Lineare Listen haben erstmal sehr viele Nachteile...Die Datenstruktur ist nicht dynamisch (schwer zu erweitern)Das Suchen in Arrays ist nur schwer in O(log(n)) möglich, da die binäre Suche sehr viel extraspeicher benötigt, und Sprungsuchen / Interpolationssuchen häufig nicht in O(log(n)) funktionierenSortierverfahren sind oftmals problematisch, da quicksort ggf. eine schlechte Worst-Case Komplexität hat. Alle Elemente müssen nebeneinander im Speicher liegen, d.h. es gibt ein Limit wie groß ich ein Array machen kann.Dagegen sind Bäume:Dynamisch (sehr einfach zu erweitern, da man einfach nur Pointer hinzufügen muss) Suche funktioniert aufbaubedingt IMMER in O(log(n)) Mit heapsort lässt sich immer im Worst-Case in O(n*log(n)) sortierenDie Datenstruktur kann beliebig groß werden (man muss nur Pointer hinzufügen).Meine Frage also, warum sollte man lineare Listen verwenden, und Warum lernt man x verschiedene Sortierverfahren von Insertion, Selection, Merge, Bubble & Quicksort für lineare Listen, wenn die einfachste Lösung ist einfach Bäume zu verwenden?

Warum sollte man Lineare Listen (arrays) als Datenstruktur verwenden?

Lineare Listen haben erstmal sehr viele Nachteile...

Die Datenstruktur ist nicht dynamisch (schwer zu erweitern)
Das Suchen in Arrays ist nur schwer in O(log(n)) möglich, da die binäre Suche sehr viel extraspeicher benötigt, und Sprungsuchen / Interpolationssuchen häufig nicht in O(log(n)) funktionieren
Sortierverfahren sind oftmals problematisch, da quicksort ggf. eine schlechte Worst-Case Komplexität hat.
Alle Elemente müssen nebeneinander im Speicher liegen, d.h. es gibt ein Limit wie groß ich ein Array machen kann.

Dagegen sind Bäume:

Dynamisch (sehr einfach zu erweitern, da man einfach nur Pointer hinzufügen muss)
Suche funktioniert aufbaubedingt IMMER in O(log(n))
Mit heapsort lässt sich immer im Worst-Case in O(n*log(n)) sortieren
Die Datenstruktur kann beliebig groß werden (man muss nur Pointer hinzufügen).

Meine Frage also, warum sollte man lineare Listen verwenden, und Warum lernt man x verschiedene Sortierverfahren von Insertion, Selection, Merge, Bubble & Quicksort für lineare Listen, wenn die einfachste Lösung ist einfach Bäume zu verwenden?

2 Antworten

Vom Beitragsersteller als hilfreich ausgezeichnet

tunik123

30.01.2023, 12:26

Beide Datenstrukturen haben ihre Vor- und Nachteile.

Die beim Anlegen eines Arrays vorzugebende Größe des Arrays ist durchaus ein Nachteil.

Wenn man das Array sortiert hat, kann man in O(log(n)) suchen. Wozu man da viel Extraspeicher benötigt, ist mir unklar.

Für Arrays funktioniert übrigens auch Heapsort, ohne Extraspeicher.

Für einen balancierten binären Baum braucht man für jeden Knoten zusätzlich zwei Pointer und mindestens zwei Extra-Bits, für ein Array nicht.

Die Implementierung von Bäumen ist nicht gerade trivial.

Die Tatsache, dass im Array die Elemente nebeneinander liegen, wird zum Vorteil, wenn man den Index eines Elements kennt oder einfach nur über alle Elemente iterieren will.

In der Praxis verwende ich beide Strukturen, je nach Bedarf.

W00dp3ckr

30.01.2023, 12:04

Weil Bäume keinen Lookup des n-Ten Elements in konstanter Zeit können. Und weil nebeneinander liegende Werte im Array auch nebeneinander im Speicher liegen.

Arrays und Listen sind zwei verschiedene Datenstrukturen.

J0T4T4

30.01.2023, 15:58

Wo unterscheiden sich Arrays und Listen?

Zwnow

30.01.2023, 21:40

@J0T4T4

Bei Arrays musst du eine Größe festlegen, für diese wird Speicher reserviert. Listen kannst du dynamisch vergrößern. Wie sich das mit dem Speicher bei Listen verhält weiß ich allerdings nicht aus dem Stehgreif.

W00dp3ckr

30.01.2023, 23:06

@J0T4T4

Eine klassische Liste ist eine Struktur, bei der jeweils ein Element den Zeiger aufs nächste Element enthält.

W00dp3ckr

30.01.2023, 23:07

@W00dp3ckr

Anhängen in O(1), sonst ist Zugriff auf ein beliebiges Element O(n)

J0T4T4

30.01.2023, 23:41

@W00dp3ckr

Das sind Linked Lists, Lists dürfte einfach nur der Oberbegriff sein.

Ähnliche Beiträge

Quicksort vs mergesort laufzeit?

Quicksort : worst case (n^2) , average case/best case (n log n) Mergesort : immer n log n

Ich versteh nicht wieso man sagt dass quicksort besser sein soll, wenn mergesort immer mindestens genau so schnell ist wie der best case von quicksort. Hat da jemand eine ahnung wann es sinn macht quicksort zu benutzen ?

...zum Beitrag

Unterschied zwischen linearem Wachstum und "super linearem Wachstum"?

Wir haben in Informatik momentan als Thema Sortierverfahren und jeder im Kurs soll eines vorstellen. Nun, ich habe den Quicksort zugeteilt bekommen und ich soll mich bei diesem ebenfalls mit der Laufzeit auseinandersetzen. Beim Quicksort beträgt die Laufzeit im worst-case O(n^2), was ich ja noch verstehe. Im average und im best-case beträgt diese aber O(n*log(n)) und ich weiß bei Leibe nicht was das heißen soll.

Ich hatte daraufhin mal auf Wikipedia nachgeschaut, aber da stand nur das es sich um ein super lineares Wachstum handelt und ich habe leider keine Ahnung, was das heißen soll...

Wäre nett, wenn das irgendwer zufällig wissen sollte. :)

...zum Beitrag

Laufzeit InsertionSort/Countsort (Worst Case)?

Sei n die Eingabgelänge des Arrays und k die Größe des Wertebereichs .

Es gelte, dass k=n

ist. Somit wächst die Größe des Wertebereichs linear mit der Größe der Eingabe.

Welcher der beiden Algorithmen (Insertionsort bzw. Countsort) weist für große n im Worst Case unter diesen Annahmen eine bessere Laufzeit auf?

Kann ich auch eine Begründung kriegen, oder mir erklären was ich machen muss um das rauszufinden ?

...zum Beitrag

Schema für einen Durchlauf durch eine lineare Liste?

Datenstruktur Liste .

ich freue mich über hilfreiche Rückmeldung:)
Vielen dank im Voraus

...zum Beitrag

Programm schreiben das Primzahlen mithilfe von Arrays herausfindet?

Hallo,

muss eine Funktion in C schreiben, die Primzahlen in einem Array herausfindet. Wie macht man sowas ohne, dass man Pointer verwenden darf?

...zum Beitrag

ChatGPT offline weiterentwickeln?

Hallo,

aktuell kann man mit ChatGPT über die Website von OpenAI sprechen.

Allerdings würde ich gerne die KI offline nutzen und auch die Datenbank der Trainingsdaten ergänzen mit wissen und treibern z.b. für Kameras, Servomotoren, Microcontrolern.

ChatGPT müsste Open Source sein wo kann ich die KI mit samt den Trainingsdaten downloaden oder muss ich hierfür erst bei Elon Musk anfragen ?

Ich wünsche euch allen einen schönen Tag.

...zum Beitrag

Wie begründet man die Anwendung der Sortieralgorithmen auf gegebene Beispiele?

Hallo liebes Forum,
ich versuche mich gerade etwas an dem Thema Sortieralgorithmen.
Die Theorie von Insertion Sort, Quicksort, Mergesort, Heapsort, Selection Sort, Bubblesort ist mir bekannt, habe auch jeden schon mal selbst programmiert und etwas getestet, nur war mir die Anwendung nie richtig klar.
Besser gesagt, wie und wann werden die außerhalb der Theorie verwendet.

Mir ist klar, dass man Insertion Sort und Selection Sort wegen ihrer mäßigen Worst Case Laufzeit nur für geringe Datenmengen einsetzt, bzw Insertion Sort auch, wenn die Daten schon vorher stark sortiert wurden.

Quicksort, Mergesort und Heapsort, weißen für großen Datenmengen die besten Laufzeiten auf, wobei man bei Quicksort darauf achten muss, das die zu sortierenden Elemente nicht schon sortiert sind, denn sonst geht die Laufzeit im Worst Case katastrophal nach oben. Weiter ist wenn es um die Speicherkapazität des Systems geht, Heapsort und vielleicht auch Qicksort zu bevorzugen, denn dank des speicherns der Ergebnisse auf ein Hilfsarray ist Mergesort ziemlich Speicher verbrauchend.

Nun habe ich diese ehemalige Klausuraufgabe aus einer Uni gefunden wobei es natürlich keine richtige Musterlösungen gab, sondern nur ein Hinweis (steht in Klammern), ich aber gerne einmal wüsste, wie man es richtig lösen könnte.

Aufgabe:

"Wählen Sie den effizientesten Algorithmus um diese Probleme zu lösen, begründen Sie außerdem ihre Entscheidung mittels der Kriterien Laufzeit und Stabilität.
Eine kurze Begründung ist ausreichend! "

An einer Verkehrskreuzung wurde über 10 Tage hinweg die Anzahl der Autos gezählt, die links abbiegen. Die Tageswerte liegen zwischen 10 und 2000 Autos. (SelectionSort)
An hunderten Wetterstationen Weltweit werden seit 1950 Temperaturwerte gesammelt. Die Werte werden auf ganze Zahlen gerundet. Der niedrigste Wert ist -89°C und der höchste 70°C. Insgesamt sind es ca. 1 Mrd. Werte. (CountSort)
Im Sonnensystem des Sterns "Sonne" gibt es 8 Planeten. Ihr Abstand zur "Sonne" ist zwischen 58 Mio. Km und 4495 Mio. Km. Die Planeten sollen Danach sortiert werden. (BubbleSort)
Ein Online-Shop hat ein Bewertungssystem für Seine Produkte, auf der Startseite sollen alle Produkte absteigend nach der Anzahl ihrer Bewertungen angezeigt werden. Diese Anzahl liegt in einem Array von Structs als Wert vor. Die Startseite soll jede Minute aktualisiert werden, somit wird der Algorithmus 1x pro Minute laufen. Da der Shop noch sehr klein ist, kommen selten neue Bewertungen zu Produkten dazu. (InsertionSort)
Ein neuer Zufallsgenerator hat 1 Mrd. Zahlen mit max. 512 Bit generiert. Um zu prüfen, wie gleichmäßig die Zahlen verteilt sind, sollen sie sortiert werden. (MergeSort)

Über eure Hilfe wäre ich sehr Dankbar

Lara

...zum Beitrag

?Benutzte Grafikkarte (3060) gekauft, sollte ich sie zurückschicken?

Also: ich habe über Mindfactory eine (angeblich) neue Grafikkarte gekauft. Allerdings gehe ich davon aus, dass die Grafikkarte bereits benutzt ist, weil die Verpackung recht abgenutzt aussieht. Sollte ich die Grafikkarte zurückschicken oder nicht? Was wären die worst-case Szenarien und realistische Konsequenzen wenn ich eine benutzte Grafikkarte verwende? Die Grafikkarte heißt MSI 3060 ventus OC.

...zum Beitrag

Algorithmus herausfinden von Zahlenfolge?

Ich habe eine Zahlenfolge, wie z.B. 5, 10, 18, 32, 52. Die mehr oder weniger eine Kurve darstellen. Hab bei Log,Sin,Cos aber nicht so wirklich aufgepasst...

Wie kann ich den zugrundeliegenden Algorithmus herausfinden?

Edit:

Es geht um Exp/Lvl bei einem Videospiel. Wie das System funktioniert weiß ich leider nicht, aber ich habe ziemlich viele Werte:

5, 10, 18, 32, 52, 81, 119, 168, 231, 307, 400, 510, 639, 788, 959, 1154, 1375

Ich würde die Zahlenreihe gern erweitern ohne die Kurve zu verändern. Sie ist leider nicht linear.

...zum Beitrag

Informatik "Rätsel"?

Programmiersprache: JavaWie stellt man bei der Datenstruktur Queue Objekte nicht hinten sondern vorne an? Also vom Code her.Kontext/Hintergrund von dieser Frage: Ich habe eine PriorityQueue. Doch dann soll plötzlich ein neues Objekt hinzugefügt werden, welches eine höhere Priorität als alle bereits in der PriorityQueue vorhandenen Objekte hat. (Da das hinzuzufügende Objekt ja die höchste Priorität hätte, müsste es ganz vorne in der PriorityQueue stehen).
Natürlich habe ich mir, bevor ich die Frage hier auf GF stelle, selbst nachgedacht, wie man das Problem lösen könnte. Bis jetzt ist mir aber nur

first = new QueueInhalt(pObject, pPriority);

eingefallen. Ich komme beim setNext(), also wenn der neue, eingefügte, Knoten QueueInhalt seinen Next - Link auf den ursprünglich an derselben Stelle (ganz vorne) gewesenen Knoten QueueInhalt setzt. (Wenn man ein Objekt hinten anstellt, schön nach FIFO halt, hätte ich kein Problem mit dem Setzen der next - links und first - links. Aber vorne anstellen? Keine Ahnung, wie das gehen soll.)
Danke und ein "Hilfreich" schonmal für eure Antworten😀

public void add(ContentTypePerson pObject, int pPriority) {
    QueueInhalt inhaltsobjekt = new QueueInhalt(pObject, pPriority);
    if (first == null) { //Wenn kein Objekt in der Queue vorhanden ist
    first = new QueueInhalt(pObject, pPriority);
    } else if (pPriority > first.getPriority()) {
    first = new QueueInhalt(pObject, pPriority);
//...?    
    }
}

...zum Beitrag

Java Print Pyramid?

Hey Leute könnte mir jemand einen Tipp geben? Auf der Konsole muss Folgendes ausgegeben werden:

Man darf keine zusätzlichen Arrays oder anderen komplexen Datenstrukturen außer numbers verwenden:

public class JavaProjekt {
  public static void main(String[] args) {
    // die erste Zahlensequenz
    int[] numbers = { 1, 2, 3, 4, 5 }; // zum Beispiel //

    TODO ihr Code hier
  }
}

Mein Code:

int [] numbers = new int [] { 1, 2, 3, 4, 5 };

for (int i = 5; i >= numbers[0]; i--) {
  for (int j = 1; j <= i; j++) {
    System.out.print(j);
  }

  System.out.println();
}

...zum Beitrag

LinkedList in Java sortieren beim Einfügen eines neuen Elements?

Ich habe hier den Code geschrieben, um ein neues Element einzufügen und danach die Liste zu sortieren.

Ich weiss, dass beides (Algorithmus für einfügen & Algorithmus fürs Sortieren) einzeln eigentlich funktionieren sollte. Aber die Kombination davon in einer Methode scheitert. Sieht jemand den Fehler.

Herzlichen Dank im Voraus!

...zum Beitrag

C: Was kann eine verkettete Liste, was ein Array nicht kann?

Hab gerade eine Frage über verkettete Listen gesehen, und jetzt denke ich mir: Was genau kann denn so eine verkettete Liste mehr als ein Array/Pointer?

Mit realloc kann ich die größe des arrays ja auch während das Programm läuft verändern.. mehr vorteile einer linked list finde ich nicht. also: Warum sollte man eine Linked List hernehmen?

...zum Beitrag

Quicksort mit median pivotisierung?

Hey, ich habe den Quicksort Algorithmus folgendermaßen beschrieben bekommen:

Nun habe ich eine Methode lowerMedian(), die den Median einer Liste bestimmt. Wie genau muss ich diese Methode nun im Quicksort algorithmus einsetzen, damit dieser als Pivot Element immer den Median nimmt, die Laufzeit also O(log(n)) ist?

...zum Beitrag

Was möchtest Du wissen?

Deine Frage stellen