0 Daumen
376 Aufrufe

Algorithmen mit polynomieller Laufzeit \( \left.\left(\operatorname{Time}_{A}(n) \in \mathcal{O}\left(n^{k}\right)\right)\right) \) werden in der theoretischen Informatik oft als gute oder effiziente Algorithmen bezeichnet. Praktisch ist jedoch lange nicht jeder solche Algorithmus auch wirklich sinnvoll.

Um dies zu veranschaulichen, vergleichen wir hier für sieben Algorithmen \( A_{1}, A_{2}, \ldots, A_{7} \) die Größen der Funktionen Time \( _{A_{i}}(n), 1 \leq i \leq 7 \), für verschiedene Eingabewerte.

i1234567
Time \( _{A_{i}}(n) \)\( \left\lceil\log _{2}(n)\right\rceil \)\( \lceil\sqrt{n}\rceil \)\( 2 \cdot n \)\( \left\lceil n \cdot \log _{2}(n)\right\rceil \)\( n^{2} \)\( n^{3} \)\( n^{4} \)

a) Wie viele Schritte benötigen die Algorithmen \( A_{1}, A_{2}, \ldots, A_{7} \) zur Bearbeitung von Eingaben der Größe \( n \in\left\{10^{j} \mid 1 \leq j \leq 10\right\} ? \)

b) Wie viel Zeit benötigen die Algorithmen \( A_{1}, A_{2}, \ldots, A_{7} \) zur Bearbeitung von Eingaben der Größe \( n \in\left\{10^{j} \mid 1 \leq j \leq 10\right\} \) unter der Annahme, dass ein Schritt eine Nanosekunde ( 1 Nanosekunde \( =10^{-9} \) Sekunden) dauert?

c) Welche Algorithmen würden Sie auch für große Instanzgrößen \( n \) als praktisch einsetzbar bewerten?

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community