data structures and algorithms in swift

Datenstrukturen und Algorithmen in Swift

Dies sind die Zusammenfassung meiner Erkenntnisse aus einem Udemy -Kurs: "Datenstrukturen & Algo in Swift"

Zeitkomplexität:

1. Ständige Zeit
2. Lineare Zeit
3. Quadratische Zeit
4. Logarithmische Zeit - binäre Suche
5. Quasilinearzeit

Knoten:

• Wurzel
• Kind -> linkes Kind und rechte Kind
• Blatt

Verlinkte Liste

• Elemente werden durch Referenz namens Knoten miteinander verbunden

• Der 1. Knoten in der verknüpften Liste wird als Kopf bezeichnet

• Der letzte Knoten heißt Tail Knoten

  Vorgänge: - Push - Anhängen - Einfügen - Pop - Removelast - Entfernen

Stack (LIFO)

• Drücken
• Pop

Warteschlange (FIFO)

• Spähen
• Enqueue
• Dequeue

Rekursion

• Basisfall - der die Rekursion stoppt.
• Rekursiver Fall

Bäume:

• Tiefe Erste Traversal
• Level Order Traversal
• Suchen
• Binärbaum (kann maximal von: 2 Kindern haben - links und rechts)
  • In der Reihenfolge von Traversal -> linke -> Knoten -> rechtsChild
  • Nachbestellung von Traversal -> linke -> rechter Kind -> Knoten
  • Vorbestellverlust -> Knoten -> linke -> rechtsChild
• Binärer Suchbaum

Lineare Suche

• An)

Binäre Suche

• Sortiertes Array
• Mittelindex - links oder rechts
• Beste Zeit: o (1)
• Schlimmste Zeit: o (log n)

Blasenart

• Ich sortiert
• Beste Zeit: o (n) (falls bereits sortiert)
• Schlimmste Zeit: o (n^2)

Auswahlsart

• Tauschen Sie das Mindestelement im Array mit dem aktuellen Index aus
• Wechseln Sie zum nächsten Index und wiederholen Sie Schritt 1
• Beste Zeit: o (n^2)
• Schlimmste Zeit: o (n^2)

Insertion -Sortierung

• Ich sortiert
• Beste Zeit: o (n)
• Schlimmste Zeit: o (n^2)

Graph:

Bestehen aus

• Scheitelpunkte / Scheitelpunkt
• Kanten / Kante

Arten von Grafiken:

• Gewichtete Grafiken
• Regie Graphen
• Ungerichtete Graphen (bidirektional)

Adjazenzliste

• Am häufigsten/am häufigsten verwendeten Weg, um eine Grafik zu erstellen und darzustellen