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 Fragesteller 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 Fragen

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 ?

...zur Frage

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. :)

...zur Frage

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?

...zur Frage

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.

...zur Frage

Bäume/Informatik/Tiefensuche: Wie funktioniert die in-order-Traversierung?

Ich verstehe die in-order bei der Traversierung nicht ganz. Zumindest nicht im Code.

Man fängt bei der 5 an und läuft rekursiv bis zur 1, also immer nach links. Danach gebe ich die 1 aus. Danach würde die 3 ausgegeben werden, sprich man klettert wieder hoch.

Ich verstehe nicht, wie das Hochklettern funktioniert. Weil nach der 1 würde man doch nach rechts springen wollen, was nicht geht, weil die 1 keine Kinder hat. Dasselbe nachdem ich die 1-3. und die 4 ausgegeben habe: Wie springe ich wieder hoch zur 5?

Also im Pseudocode verstehe ich das Prinzip schon. Immer links, Wurzel, rechts. Aber im richtigen Code nicht.

Ich habe diesen Codeabschnitt von ChatGPT:

def in_order_traversal(root):
  if root is not None:
    # Zuerst den linken Teilbaum durchlaufen
    in_order_traversal(root.left)

    # Dann den Wurzelknoten besuchen
    print(root.value)

    # Schließlich den rechten Teilbaum durchlaufen
    in_order_traversal(root.right)

...zur Frage

Korrektheitsbeweis Algorithmus?

Hallo liebe Community,

ich habe eine Aufgabe bekommen in welcher ich Pseudocode entwickeln soll. Meinem Algorithmus wird ein Array an Zahlen gegeben A[1, n] mit n Einträgen. Ich soll in diesem Array die Senken zählen. Eine Senke ist dabei eine Position i [2, n - 1] für die folgendes gilt: A[i - 1] > A[i] < A[i + 1].

Meiner Auffasung nach bedeutet das nun, dass z.B. das Array [1, 3, 2, 4, 3, 5] zwei Senken hat. Nämlich einmal der dritte Eintrag und der fünfte Eintrag.

Mein Pseudocode sieht folgendermaßen aus:

Input: A[1, n] mit n Einträgen
Output: Anzahl der Senken

counter := 0
for j := 2 to n - 1 do
  val := A[j]
  if val < A[j - 1] and val > A[j + 1] do
    counter := counter + 1

Mein Java Code dazu sieht folgendermaßen aus:

public static int countSenken(int[] arr) {
  int counter = 0;
  for (int i = 1; i < arr.length - 1; i++) {
    int val = arr[i];
    if (val < arr[i - 1] && val < arr[i + 1]) {
      counter++;
    }
  }
}

Nun soll ich die Korrektheit meines Algorithmus' beweisen. Wir haben das schonmal an dem Beispiel des Insertionsort Algorithmus' gemacht. Die herangehensweise ist ja eigentlich, dass man eine Schleifeninvariante aufstellt und diese dann mittels Induktion beweist. Mein Problem ist jetzt aber, dass ich diese Schleifeninvariante nicht aufstellen kann. Beim Insertionsort, da beweist man ja die Sortiertheit und da verändert sich ja das Array. Aber bei diesem Algorithmus jetzt da verändert sich das Array ja gar nicht.

Ich weiß halt, dass n >= 3 sein muss damit der Algorithmus überhaupt funktioniert. Kann mir vielleicht jemand einen Ansatz geben wie ich die Korrektheit beweise?

Ich wäre euch allen sehr dankbar :)

...zur Frage

Pivotwahl bei Quicksort und Quickselect?

Guten Abend,

ich bräuchte mal kurz Hilfe bei folgenden Aufgaben, bitte. Es geht mir darum, dass ich einfach nicht versteh', was zu tun ist. Wir hatten in der Vorlesung den Quicksort-Algorithmus. Ich weiß, dass bei Quicksort das zu sortierende Array in immer kleiner Teilarrays eingeteilt wird, wobei das größere Array zuerst auf den Stack gelegt wird. Das Pivotelement ist entweder das linke oder das rechte und man setzt dann links und rechts einen Pointer am entsprechenden Teilarray. Ist das erste Element des zu sortierenden Teilarrays, welches größer als das Pivotelement ist, gefunden, und es findet sich vom rechten Pointer aus das erste Element, welches kleiner als das Pivotelement ist, so werden diese vertauscht. Bei Überkreuzungen tausche jenes Element auf dass der linke Pointer zeigt mit dem Pivotelement. So hatten wir's zumindest in der Vorlesung (Partitionswahl). Zu den Aufgaben

Aufgabe 1

Ein wichtiger Faktor für die Laufzeit von Quicksort und Quickselect (das Auswahlverfahren des k-kleinsten Elements analog zu Quicksort) ist die Wahl des Pivotelements. Das Pivotelement sollte die zu sortierende Folge in zwei möglichst gleich große Teilfolgen aufspalten.Gegeben sei eine unsortierte Folge mit n paarweise verschiedenen Elementen. Weiterhin sei r(x) die Position des Elements x in der sortierten Folge. Eine mögliche Strategie für die Pivotwahl ist:Wähle uniform zufällig 7 Elemente aus der Eingabefolge und gib das viertkleinste als Pivotelement aus. Dabei können Elemente in der Auswahl mehrmals vorkommen (Ziehen mit Zurücklegen)

.a) Berechne die Wahrscheinlichkeit für das Ereignis: n/4 < r(Pivot) ≤ 3n/4.

b) Nach wie vielen unabhängigen Wiederholungen der Pivotwahl ist zu erwarten, dass der Rang des Pivotelements das erste Mal außerhalb des Intervalls aus Aufgabenteil a) liegt? Hinweis: Du darfst annehmen, dass n= 4·kfür ein k∈N.

Aufgabe 2

Konstruiere eine Folge der Länge7, so dass Quickselect bei Verwendung der Pivotfunktionpivot(links, rechts) =⌈(links+rechts)/2⌉ auf der Suche nach dem viertgrößten Schlüssel die Problemgröße stets nur um 1verringert. Der Algorithmus soll insgesamt also sieben Schritte benötigen, bis er terminiert. Wende Quickselect auf Ihre Folge an, um die Korrektheit zu zeigen

Ansatz Ich verstehe hier nicht, wie n/4 gemeint ist. Wir hatten in der Vorlesung immer das Pivotelement ganz links oder ganz rechts. Jetzt steht hier "Pivot(links,rechts) = [(links+rechts)/2]. Greift man sich also da Element in der Mitte? Das ist bei einer Folge der Länge 7 doch nicht möglich, oder? WIe gehe ich allgemein vor um eine solche Folge zu finden.

Jensek81

...zur Frage

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!

...zur Frage

C++ alle Kombinationen eines Strings mit der Länge L mit zurücklegen?

Hallo,

ich möchte so etwas wie einen Password-List-Generator schreiben, komme aber nicht auf die richtige Rekursionsfunktion.

Es soll zum Beispiel aus einem Zeichensatz wie "abcdef" und der information L = 9 Passwörter im vector<string> zurückgegeben werden, bei denen jeder der Buchstaben an jeder Position 0, 1, .., 9 mal vorkommt, wie beim Passwortgenerator "crunch".

Hat mir jemand ein Code-Beispiel parat?

Viele Grüße

Lukas Z

...zur Frage

Themenbereiche Informatik - Eure Lieblingsthemen?

Es kann sein, dass ich nicht alles angegeben habe, aber dafür gibt es den Bereich "Anderes".

Danke Euch.

...zur Frage

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?

...zur Frage

Komplexität von Funktion bestimmen?

Das ist die Funktion. Leider gibts für die Aufgabe keine Lösung, aber ich hätte gesagt, dass die innere Schleife log_2(n) Höchstens log_2(n) Durchläufe hat, weil k ja immer mindestens halbiert wird. Zusammen mit der äußeren Schleife wäre das n * log n

Aber die äußere Schleife macht ja eigentlich nichts, wenn k = 0 ist. Muss das n dann trotzdem mitberechnet werden oder würde hier auch ein log n reichen, sodass es auf log^2 n rauslaufen würde?

...zur Frage

Kann mir jemand helfen?

Ich soll ein Struktogramm für diese Aufgabenstellung erstellen: Erstellen Sie einen Algorithmus, der den Benutzer nach zwei Zahlen Z1 und Z2 fragt und der anschließend ausgibt, ob

• Z1 größer als Z1 ist, oder

• Z1 kleiner als Z2 ist, oder

• beide Zahlen gleich sind.

Mein Struktogramm sieht so aus:

Bei der Auswertung im Programm bekomme ich immer Fehler und ich weiß nicht was an meinem Struktogramm falsch ist:

...zur Frage

Java Arrays Buchstaben als Zahlen ausgeben?

Hi, ich habe eine Aufgabe, bei der ich schon die Aufgabenstellung nicht verstehe, geschweige denn, die Aufgabe selbst.

Aufgabe: (Methode: toDoubleArray)

Modifikatoren: public und static, Rückgabetyp: double-Array , Methodenname: toDoubleArray , Übergabeparameter: String

Schreibe eine Methode, die ein double-Array erzeugt und es mit den einzelnen Zeichen (char) aus dem String befüllt.
Allerdings werden diese Werte vor Zuweisung noch nach double gecastet. Anschließend wird das double-Array zurück gegeben.

Beispiel: Der Aufruf toDoubleArray("Hallo") liefert ein Array, das folgendermaßen befüllt ist: [72.0, 97.0, 108.0, 108.0, 111.0]

Das casten verstehe ich. Ist ja nur eine Typumwandlung von char nach double und geschieht automatisch, weil char in double passt. Hier ein Beispiel:

public static void main(String [] args) {	

		char t = 'a';

		System.out.println(t);
        System.out.println((double) t);
  }
}		

Ausgabe : a
          97.0

> char als Buchstabe und als Zahl

Wie soll ich jetzt den ersten Teil der Aufgabe machen, also die Zeichen (char) aus dem String ins Array bringen????

Wie füge ich die Zeichen in erster Linie ins Array?

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen