Ich löse eine Algorithmusfrage und meine Analyse ist, dass sie auf O (2 ^ sqrt (n)) laufen würde. Wie groß ist das? Entspricht es O (2 ^ n)? Ist es noch nicht polynomielle Zeit?
big-o
algorithm-analysis
Gaara
quelle
quelle
Antworten:
Dies ist eine interessante Frage. Glücklicherweise ist es nicht besonders schwer, wenn Sie erst einmal wissen, wie man es löst.
Für die Funktionen f : N → R + und g : N → R + haben wir genau dann f ∈ O ( g ), wenn lim sup n → ∞ f ( n ) / g ( n ) ∈ R ist .
Eine Funktion f : N → R + hat genau dann höchstens ein Polynomwachstum, wenn eine Konstante k ∈ N existiert, so dass f ∈ O ( n ↦ n k ) ist. Lassen Sie uns dies für beliebige, aber feste k ∈ N herausarbeiten .
lim sup n → ∞ 2 ( n 1/2 ) / n k =
lim n → ∞ 2 ( n 1/2 ) / n k =
lim n → ∞ e log (2) n 1/2 / e log ( n ) k =
lim n → ∞ e log (2) n 1/2 - log ( n ) k = ∞ ∞ R.
Die erste Gleichheit ist wahr, weil sowohl der Nominator als auch der Nenner monoton wachsende stetige Funktionen sind. Die zweite Gleichheit verwendet die Identität x y = e log ( x ) y . Die Grenze ist nicht endlich, da der Exponent im endgültigen Ausdruck oben nicht begrenzt ist. Ohne einen formalen Beweis kann angenommen werden, dass bekannt ist, dass n 1/2 log ( n ) asymptotisch dominiert . Daher übersteigt die fragliche Funktion das Polynomwachstum.
Sein Wachstum ist jedoch streng geringer als exponentiell, wobei Exponential (von mir zu diesem Zweck) als O ( n ↦ 2 c n ) für c > 0 definiert wird. Dies zu zeigen ist noch einfacher.
lim sup n → ∞ 2 c n / 2 ( n 1/2 ) = lim n → ∞ 2 c n - n 1/2 = ∞ ∞ R.
für jedes feste c > 0. Daher liegt die Komplexität der Funktion wirklich irgendwo zwischen Polynom und Exponential.
quelle
Wie groß ist das? Nun, O (2 ^ sqrt (n)) ist genau wie groß es ist :-(
Um eine Vorstellung davon zu bekommen, was es bedeutet, stellen Sie sich vor, Ihr Algorithmus wäre nicht nur O (2 ^ sqrt (n)), sondern es dauert tatsächlich genau 2 ^ sqrt (n) Nanosekunden auf Ihrem Computer:
n = 100: 2 ^ 10 = 1024 Nanosekunden. Überhaupt keine Zeit. n = 1000: 2 ^ 31.xxx = 2 Milliarden Nanosekunden. Zwei Sekunden, das fällt auf. n = 10.000: 2 ^ 100 ≈ 10 ^ 30 Nanosekunden = 10 ^ 21 Sekunden = 30 Billionen Jahre.
Dies ist viel besser als 2 ^ n Nanosekunden, wobei n = 100 30 Billionen Jahre dauern würde, aber die Größe der Probleme, die Sie lösen können, ist immer noch recht begrenzt. Wenn Sie ein Problem als "lösbar" betrachten, wenn Ihr Computer es in einer Woche lösen kann, sind das ungefähr 6 x 10 ^ 14 Nanosekunden, das sind ungefähr n = 2.400. Andererseits können bis zu n = 400 in einer Millisekunde gelöst werden.
(In der Praxis dauern für n = 10.000 sowohl O (2 ^ sqrt (n)) als auch O (2 ^ n) genau die gleiche Zeit: Zu lange, um darauf zu warten.)
Es überschreitet jedes Polynom. Nehmen Sie einen anderen Algorithmus, der n ^ 1000 Sekunden dauert. Was für n = 2 praktisch unlösbar ist. Dieser Algorithmus dauert länger, bis n ungefähr 885 Millionen beträgt. Aber wirklich, wen interessiert das? Zu diesem Zeitpunkt beträgt die Anzahl der Jahre, die beide Algorithmen benötigen, 9.000 Stellen.
quelle