Laufzeit des Algorithmus bei gegebener zeitlicher Komplexität

Question

Laufzeit des Algorithmus bei gegebener zeitlicher Komplexität

Algorithmen
Asymptotik
Mathematik
Analyse-von-Algorithmen
Rechenkomplexität

Taya Mbo

c) Nehmen Sie an, dass die Algorithmen A1 und A2 eine Rechenkomplexität von haben $O(n \log(n))$ Und $O(n^3)$ bzw. Beide Algorithmen benötigen ungefähr $100$ Sekunden, um bei der Dateneingabe der Größe zu laufen $n = 10,000$ . Bestimmen Sie (auf die nächste Sekunde genau) die Zeit, die jeder Algorithmus benötigt, um bei einer Dateneingabe der Größe ausgeführt zu werden

ich. $n = 1,000$

ii. $n = 100$

Ich habe in den letzten Tagen versucht, einen Weg zu finden, das zu lösen, aber ich stecke völlig fest. Jemand anderes hatte ein ähnliches Problem, aber als ich versuchte, ihre Methode anzuwenden, funktionierte es nicht. Bitte helfen Sie mir, ich habe am Dienstag eine Prüfung in diesem Bereich

Fabio Somenzi

Erstens gibt die Big-Oh-Notation nur Obergrenzen an. Soweit uns mitgeteilt wird, können beide Algorithmen in linearer Zeit ablaufen. Zweite,

f_{1} (n) = k_{1} n \log (n)

$f_1(n) = k_1 n \log(n)$ Und

f_{2} (n) = k_{2} n \log (n) + 99

$f_2(n) = k_2 n \log(n) + 99$ sind beide

O (n \log (n))

$O(n \log(n))$ , aber falls

f_{1} (10^{4}) = f_{2} (10^{4}) = 100

$f_1(10^4) = f_2(10^4) = 100$ , Dann

k_{1} = 100 k_{2}

$k_1 = 100 k_2$ und deren Laufzeiten für

n = 10^{3}

$n=10^3$ oder

n = 10^{2}

$n=10^2$ wird ganz anders sein.

Antworten (1)

Laufzeit des Algorithmus bei gegebener zeitlicher Komplexität

Erstens gibt die Big-Oh-Notation nur Obergrenzen an. Soweit uns mitgeteilt wird, können beide Algorithmen in linearer Zeit ablaufen. Zweite, $f_1(n) = k_1 n \log(n)$ Und $f_2(n) = k_2 n \log(n) + 99$ sind beide $O(n \log(n))$ , aber falls $f_1(10^4) = f_2(10^4) = 100$ , Dann $k_1 = 100 k_2$ und deren Laufzeiten für $n=10^3$ oder $n=10^2$ wird ganz anders sein.

bsbb4 · Answer 1

Bitte bedenken Sie, dass ich so ziemlich nichts über Rechenkomplexität weiß.

Rufen wir die Laufzeiten für eine Größeneingabe auf $n$ $A_1(n)$ Und $A_2(n)$ bzw. Das ist uns gegeben $A_1(n) = O(n\log(n))$ was bedeutet, dass $\lim_{n \to \infty}\frac{A_1(n)}{n\log(n)} < \infty$ . Daher ist die Grenze endlich, aber wir wissen noch nicht, was sie ist. Wir können es herausfinden, indem wir die zusätzlichen Informationen verwenden, die wir erhalten: $A_1(10) = 100$ . Einstecken, wir bekommen $\frac{A_1(10)}{10\log(10)} \approx 4.3429$ . Das Gleiche tun für $A_2$ wir bekommen $\frac{A_2(10)}{10^3} = 0.1$ .

Jetzt können wir das Problem lösen:

\frac{A_{1} (1000)}{1000 Protokoll (1000)} = 4.3429 ⟹ A_{1} (1000) \approx 30 000

$\frac{A_1(1000)}{1000\log(1000)} = 4.3429 \implies A_1(1000) \approx 30\,000$

\frac{A_{2} (1000)}{1000 Protokoll (1000)} = 0,1 ⟹ A_{2} (1000) = 100 000 000

$\frac{A_2(1000)}{1000\log(1000)} = 0.1 \implies A_2(1000) = 100\,000\,000$

Der zweite Teil der Frage funktioniert genauso.

Laufzeit des Algorithmus bei gegebener zeitlicher Komplexität

Taya Mbo

Fabio Somenzi

Antworten (1)

bsbb4

Erwartete Zeit von Quicksort

Was bedeutet das Wort „Skalierbarkeit“ in Bezug auf Big O?

Berechnung der Laufzeit aus Zeitkomplexität

Was sagt Big O dir eigentlich?

Quicksort-Laufzeit

Wie man eine Wiederholungsgleichung für die Laufzeit eines Teile-und-Herrsche-Algorithmus angibt

Algorithmuskomplexität - For-Schleife innerhalb einer While-Schleife; um den Faktor 2 abnehmen

Wie hoch ist die zeitliche Komplexität, wenn bbb-Einträge ohne Ersatz von nnn-Einträgen einheitlich abgetastet werden?

Vergleich der zeitlichen Komplexität zweier Algorithmen (Ungleichheit)

Frage zu Summationen und der Θ-Notation von Laufzeiten