Big Oh - O (n) gegen O (n^2)

Question

Ich habe vor kurzem zwei Tests für eine Datenstrukturklasse abgeschlossen und ich habe eine Frage zu O (n) vs O (n^2) falsch zweimal. Ich habe mich gefragt, ob ich Hilfe bekommen könnte, um das Problem zu verstehen. Das Problem ist:

Angenommen, Algorithmus A hat Laufzeit O (n^2) und Algorithmus B hat Laufzeit O (n). Was können wir über die Laufzeit dieser beiden Algorithmen sagen, wenn n = 17?

a) Wir können nichts über die spezifische Runtimes sagen, wenn n = 17

b) Algorithmus A wird viel schneller als Algorithmus B

c) Algorithmus A läuft viel langsamer als Algorithmus B läuft

Für beide Tests beantwortete ich C basierend auf: https://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions. Ich wusste, dass B aufgrund des angegebenen Links keinen Sinn ergab. Jetzt fange ich an zu denken, dass sein A. Ich denke sein A, weil n klein ist. Wenn das der Fall ist, frage ich mich, wann ist n ausreichend groß genug, dass C wahr wäre.

Answer 1

Die Antwort ist a): Sie können nicht wirklich etwas für eine bestimmte Zahl sagen, nur die große O-Notation gegeben.

Gegenbeispiel für c: B hat eine Laufzeit von 1000 * n (= O (n)), A hat eine Laufzeit von n^2.

Answer 2

Es gibt eigentlich zwei Probleme hier.

Die erste ist die, die Sie erwähnt haben. Wachstumsordnungen sind asymptotisch. Sie sagen nur, dass es etwas n für die vorhanden ist, für jede n> n, die Funktion in irgendeiner Weise begrenzt ist. Sie sagen nichts über spezifische Werte von n, nur "groß genug".

Das zweite Problem (die Sie nicht erwähnt hat) ist, dass O ist just an upper bound (as opposed to Θ), und so auch für groß genug n man die beiden nicht vergleichen kann. Also, wenn A = √ n und B = n, dann offensichtlich B wächst schneller als A. Jedoch passen A und B immer noch die Frage, wie √ n = O (n 2 )und n = O (n).

Answer 3

Bei der Analyse von Algorithmen, speziell Big Oh, sollten Sie wirklich nur über Eingangsgrößen nachdenken, die gegen unendlich gerichtet sind. Bei einer so kleinen Größe (Zehner gegen Tausend gegen Millionen) gibt es keinen signifikanten Unterschied zwischen den beiden. Im Allgemeinen sollte O (n) jedoch schneller laufen als O (n^2), selbst wenn die Differenz weniger als einige Millisekunden beträgt. Ich vermute, das Schlüsselwort in dieser Frage ist viel.

Answer 4

Die Antwort ist A.

Big Oh Ordnung einer Funktion f (x) g (x), wenn f (x) < = K * g (x) forall x> einig reale Zahl

Big Oh von 3 * n + 2 und n ist O (n), da 4 * n größer als beide Funktionen für alle x> 2 ist. Da beide die Big-Oh-Notation der Funktionen sind gleich, können wir nicht sagen, dass sie für einen Wert in der gleichen Zeit laufen. Zum Beispiel bei n = 0 ist der Wert der ersten Funktion 2 und der zweite ist 0

Also wir kann die Laufzeiten zweier Funktionen für einen bestimmten Wert nicht genau zuordnen.

Answer 5

Meine Antwort basiert auf meiner Erfahrung in Wettbewerb Programmierung, die ein grundlegendes Verständnis der O oder Big O. erfordern genannt

Wenn Sie über die man reden schneller ist und welches ist langsamer, natürlich, Grund Berechnung ist das getan. O (n) ist schneller als O (n^2), basierend auf dem Worst-Case-Szenario wird großoh verwendet.

Wann genau passiert das? Nun, in Konkurrenzprogrammen haben wir 10^8 Daumenregel verwendet. Es ist gemein, wenn eine Algorithmuskomplexität O (n) ist und es dann um n = 10^8 mit Zeitlimit um 1 Sekunde geht, kann der Algorithmus das Problem lösen.

Aber was ist, wenn die Komplexität des Algorithmus O (n^2) ist? Nein, dann wird es etwa (10^8)^2 benötigen, was mehr als 1 Sekunde ist. (1-Sekunden-Computer kann etwa 10^8 Betrieb verarbeiten).

Also, für 1 Sekunde ist die maximale Grenze für O (n^2) um 10^4 währenddessen für O (n) kann bis zu 10^8 tun. Dies ist, wo wir deutlich die Unterschiede zwischen den beiden Komplexität in 1-Sekunden-Zeit auf einem Computer sehen können.