Rechenzeit von Komplexitätsklassen

Question

f hat eine Komplexitätsklasse O(N(logN)^2), für N = 1000 das Programm in 8 Sekunden läuft

berechnen, wie lange es dauern wird, laufen, wenn N = 1,000,000

ich die Zeit berechnet 32.000 Sekunden zu sein, aber ich bin verwirrt, weil N 1000 mal wuchs, aber die Zeit um 4000 mal erhöht. Ich dachte, da dies eine Log-Funktion ist, sollte die Faktorzunahme von N geringer sein als die der Zeit.

Sind meine Berechnungen falsch oder gibt es etwas, das ich nicht verstehe?

Answer 1

"da dies eine Protokollfunktion ist": nein, das ist eine linpolylog Funktion. Weil es einen linearen Faktor N und einen polylog one log^2(N) gibt, d.h. ein Polynom eines Logarithmus.

So wächst N um einen Faktor 1000 und log(N) um einen Faktor 2 (undisputably kleiner als 1000) so log^2(N) um einen Faktor 4, für insgesamt Faktor 4000.

Answer 2

Ihre Berechnungen sind korrekt. N(logN)^2 wächst etwas schneller als N tut. In der Tat, N Faktoren beide Komplexitäten aber (logN)^2 ist halbmondförmig und ungebunden und so größer als eine Konstante eine ausreichend große Eingabe zu erreichen.