Ich sah einen Beweis für die Komplexität eines Sortieralgorithmus, der ungefähr so lautet:
Total time complexity for the algorithm = T(n-1) + T(n-2)
Thus, Total time complexity for the algorithm <= 2 * T( n-2 )
und fuhr fort, eine Beziehung zu beweisen.
Ques: Kann ich das immer sicher annehmen? T(n) >= T(n-1) ? Wenn ich bereits versuche, die Komplexität eines Algorithmus zu beweisen, wie kann ich diesen Anspruch vorwegnehmen?
Antworten:
6 für die Antwort № 1Nein, Sie können eine solche Behauptung nicht machen.
Betrachten Sie eine Funktion:
f(0) = 1000000! (factorial of 1000000)
f(n) = 1, for n>0
Hier ist die zeitliche Komplexität der Funktion mit größerem Argument kleiner als die untere.
Von den Details hängt vor allem alles ab - im Beispiel haben Sie bereits eine Aussage
Total time complexity for the algorithm = T(n-1) + T(n-2)
was entspricht
T(n) = T(n-1) + T(n-2)
Das ist eine starke Behauptung über die Komplexität, aber es scheint nicht richtig anzunehmen
Thus, Total time complexity for the algorithm <= 2 * T( n-2 )
wie wir davon abhalten können
T(n) = T(n-1) + T(n-2)
Das
T(n) = T(n-1) + T(n-2) = (T(n-2) + T(n-3)) + T(n-2) >= 2 * T( n-2 )
vielleicht war die Behauptung das?
Thus, Total time complexity for the algorithm >= 2 * T( n-2 )
2 für die Antwort № 2
Nein, man kann diese Annahme nicht immer machen, es kommt auf die Funktion T an.
Beispielsweise:
T(0) = T(1) = 1 //no important
T(2n) = T(2n-2) //all even numbers are calculated recursivel
T(2n+1) = 1 //all odd numbers
In der obigen, für jede ungerade n: T (n) <T (n-1)
Ein praktisches Beispiel, bei dem es sich tatsächlich um eine Komplexitätsfunktion handeln könnte, ist if n muss gerade sein, und wenn nicht - wird ein Fehler zurückgegeben.
0 für die Antwort № 3
Nein, hängt vom Algorithmus ab.
Ich könnte einen Algorithmus wie folgt definieren: Für jede Eingabe von Größe n < 1000 versuchen etwas zu tun. ob n > 1000 gib eine schlüssige Entscheidung zurück.
Also für jeden n < 1000 Es könnte eine lange und ermüdende Berechnung sein, aber für n > 1000 es ist O(1)
0 für die Antwort № 4
T(n) >= 2*T(n-2) ist impliziert, für n>3, durch die Rekursionsbeziehung T(n) = T(n-1)+T(n-2).
T(n-1) ist T(n-2)+T(n-3).
Ob T stellt die Kosten eines Algorithmus dar, kann nicht negativ sein.
T(n-3) >= 0 impliziert T(n-1) >= T(n-2), und T(n) >= 2*T(n-2).
Dies ist nur eine Konsequenz der spezifischen Rekursionsbeziehung, nicht etwas, was Sie im Allgemeinen annehmen können, obwohl dies für viele Rekursionsbeziehungen gilt, die bei der Algorithmusanalyse auftreten.