8
Informatik (Fach) / A&D (Effizienz) (Lektion)
Effizienzklassen, Schranken, usw.
Diese Lektion wurde von scarvy erstellt.
Diese Lektion ist leider nicht zum lernen freigegeben.
- Welche Überlegungen führen zum Begriff der "asymptotischen Effizienz"? "Wie verhält sich Rechenzeit, wenn Eingabe groß ist?" = asymptotische Effizienz: Wachstumverhalten einer Funktion bezüglich ihrer Größe
- Wie ist die O-Klasse definiert? O(g) = f| C > 0; n0> 0; 8n n : n0 < f (n) < Cg(n) d.h. f gehört zur Klasse O(g), wenn es ab n0 durch C * g(n) nachoben beschränkt ist. g(n) soll dabei möglichst einfach beschriebensein. - Funktionen, die nicht wesentlich schneller als n wächst: root n, log n, 2n...
- Warum ist die Definition von Theta sinnvoll? Was bedeutet hier asymptotisch? Die T-Klassen begrenzen das Wachstumsverhalten nach oben undnach unten. T(g) = f| (n0,c,C) ( n> n0) cg(n)<Cg(n) - Manchmal gibt man untere und obere Schranke getrennt an, d.h. die O-Notation ergänz durch: Om (g)= f |(n0,c) (n>n0) cg(n) < f(n) T(g) = Om(g) und O(g) ---> Om(n) Funktionen wachsen mind, so schnellwie n (z.B. 2n, nlog n, n², 2^n)
- Wieso betrachtet man überhaupt den worst-case? Worst casegarantiert, dass der Bedarf nie höher ist als angegeben. Average case nimmt an, dass alle Eingaben gegebener Größe gleichwahrscheinlich sind, und kann daher täuschen.
- Asymptotische Effizienz von insert/ isort. Betrachten wir die bisherigen Ergebnisse asymptotisch, so erhaltenwir: wc-time insert e (n)av-time insert e (n)space insert e (n) wc-time isort e (n²)space isort e (n)
- Treesort beschreiben, sortTree :: Tree Integer -> [Integer]sortTree (Leaf a) = [a]sortTree (Br l r) = merge (sortTree l) (sortTree r) merge :: (Ord a) => OrdList a -> OrdList a -> OrdList amerge [] bs = bsmerge (a:as) [] = a:asmerge (a:as) (b:bs)| a <= b = a:merge as (b:bs)| otherwise = b:merge (a:as) bs
- Was bedeutet Komplexität von Algorithmen? -Algorithmische Komplexität wird daher mit Effizienz gleichgesetzt. -Unter der Komplexität (auch Aufwand oder Kosten) eines Algorithmus versteht man seinen maximalen Ressourcenbedarf. -Dieser wird oft in Abhängigkeit von der Länge der Eingabe angegeben und für große asymptotisch unter Verwendung eines Landau-Symbols abgeschätzt. -Die algorithmische Komplexität gibt die Komplexität einer konkreten algorithmischen Lösung für ein Problem an (z.B. sortieren). Die theoretische Informatik liefert Maße für die Aufwände in Zeit und Speicherplatzbedarf eines Algorithmus. (Das Maß definiert verschiedene Funktionsklassen einer Ordinalskala: logarithmisch, linear, quadratisch, ...).
- Was versteht man unter Problemkomplexität? Problemkomplexität: Unter der Annahme, dass ein Problem algorithmisch lösbar ist, kann man die Komplexität eines optimalen Algorithmus als die Problemkomplexität definieren. Damit ist die Problemkomplexität stets kleiner oder gleich der algorithmischen Komplexität irgendeines Algorithmus zur Lösung des Problems.
Anzeige