Einführung von Algorithmen Flashcards
1
Q
Was ist wichtiger als die Leistung?
A
2
Q
Wozu ist es wichtig Algorithmen zu analysieren?
A
- Die Leistung zieht oft die Grenze zwischen dem, was möglich und unmöglich ist.
- Algorithmen helfen uns, die Skalierbarkeit zu verstehen
- Leistung ist die Währung des Rechnens
3
Q
Was ist das RAM-Modell?
A
- Befehle werden nacheinander ausgeführt. (Keine Threads)
- Wir identifizieren alle Anweisungen, die in realen Computers vorkommen
- addieren, subtrahieren, multiplizieren, dividieren, werden mit konstantem Zeitaufwand veranschlagt
- Laden, Speicherm Kopieren, Verzweigungen Unterprogrammaufrufe und Return = konstante Zeit
- Präzision der Gleitkommazahlen vernachlässigbar
- Keine Begrenzung der Wortgröße
- Bei der Eingaben der Größe n, sind Integer durch (c lg (n)) Bits repräsentiert wobei c ≥ 1 ein Konstante ist.
4
Q
Welche Fälle werden bei der Laufzeit-Analyse betrachtet?
A
– Schlechtester Fall: (manchmal)
* T(n) = maximale Zeit des Algorithmus bezogen auf jede Eingabe der Größe n
–Normalfall: (normalerweise/im Durchschnitt)
* T(n) = erwartete Zeit des Algorithmus bezogen auf jede Eingabe der Größe n
* benötigen Annahme bzgl. der statischen Verteilung der Eingänge
– Bestenfalls: (trügerisch)
* Mit einem langsamen Algorithmus kann uns “täuschen”, da er bei bestimmten Inputs
schnell arbeitet.
5
Q
Was ist der Kerngedanke hinter der Asymptotischen Analyse?
A
- Ignoriere die maschinenabhängigen Konstanten
- Betrachte das Wachstum von T(n) für n → ∞ an
