Komplexitätsanalyse (Lecture 2) Flashcards
1
Q
Komplexitätsanalyse und Einheiten
A
- Beschreibung der Performance von Algorithmen bei verschiedener Eingabegröße
- diese könne entweder die Größe einer Zahl sein oder die Anzahl an Objekten
2
Q
wann haben f(n) und g(n) die gleiche Wachstumsrate?
A
falls für große n das Verhältnis durch Konstanten beschränkt ist
c <= f(n)/g(n) <= d
3
Q
wann wächst f(n) schneller als g(n)
A
wenn der limes von g(n)/f(n) 0 wird
4
Q
was ist O(f(n))
A
alle Funktionen die asymptotisch nicht schneller als f(n) wachsen
5
Q
was ist Ω(f(n))
A
alle Funktionen die asymptotisch nicht langsamer als f(n) wachsen
6
Q
was ist θ(f(n))
A
alle Funktionen die asymptotisch gleich wie f(n) wachsen
7
Q
Warum darf man Konstanten wegschmeißen?
A
Analyse ist eh nur eine Abstraktion
Dieser Faktor kann auch durch eine besser Maschine usw erzielt werden, und es ist leichter damit weiterzurechnen
8
Q
A
9
Q
A
10
Q
A
11
Q
A
