Info 2 version 3

  • Was auch immer Buchin sagt

Binäre Suche

  • Naja wir suchen mit dem "Teile und Herrsche" Konzpet
    • Wir teilen das Array was wir duchsuchen wollen auf und durchsuchen die teile weiter rekursiv
    • :)
      semmup
  • Jetzt analysieren wir den kram

  • Algorithmenanalyse

    • Wir können die Laufzeit vin rekursiven Algos als "Rekurrenz" formulieren
    • Wir stellen unsere Rekurrenz auf, da müssen wir auch berücksichtigen wie die Rekursivität der Funktion funktioniert
    • Im Fall der Binären suche können wir T(n) \leq T(\lceiln/2\rceil) + O(1) sagen, denn jeder weitere Rekursive Aufruf hat die Hälfte der Daten von dem Aufruf davor
    • Das Mastertheorem ist ein "Kochrezept" von rekurrenzen

Analyse im Mittleren Fall

  • Wir wollen schauen was "durchschnittlich" passiert
  • Wir interessieren uns in der regel für den "Worst Case", weil dann kann ja alles andere nur noch besser werden

Amortisierte Analyse

  • Jede Operation hat "kosten"
  • Diese kosten drücken aus, wie lange etwas zum laufen braucht
  • Die konkrete Frage ist dann: Was sind die Kosten für Operationen

Beispiel

  • Wir implementeren einen Zähler
  • Wir wissen, dass eine inkrementierung Kostet
  • Wenn wir uns den Zähler anschauen merken wir, dass alle Zustände gleich warscheinlich sind, da der Zähler ja alle zustände durchläuft wenn er von 0000 bis 1111 zählt

Randomisierten Algorithmen

  • Es gibt zwei arten
    • Las Vegas: Die Laufzeit hängt vom zufall ab, das Ergebnis nicht
  • Minte-Carlo-Algorithmen
    • Das Ergebnis hängt vom Zufall ab, die Laufzeit nicht

Graphen

  • Mit graphen kann man die Beziehungen zwischen Objekten darstellen
  • Graphen werden in vielen Konzepten benutzt, und bilden somit eine Grundlage für diesen Kram

Wasn das?

  • Ein Graph ist immer eine Menge Mit knoten V (Verticy) und Kanten E (Edge)
  • Ein Baum ist dann ein ungerichteter Graph, in dem es Zwischen zwei beliebigen Knoten jeweils genau einen weg gibt
    • Das bedeutet, dass es von jedem knoten zu jedem anderen knoten einen weg gibt, und somit jeder Knoten von jedem anderen Knoten erreichbar ist, wenn man jeden weg nutzen kann
    • Es gibt da mehrere Arten von Knoten
      • Wurzel: Da wo alles losgeht
      • Innere Knoten sind die, die weitere Kinder haben
      • Blätter sind die, die keine Kinder haben

Polynominielle und Non-Polynomielle Laufzeit

  • Ein Algorithmus mit polynomieller Laufzeit (oder auch Laufzeit) heißt effizient;
  • Zeume sagt hi
    • Es gibt keine Effizienten Algorithmen für manche Probleme