Wie schätze ich den Zeitaufwand? (Geburtsraten)

Beginnen wir mit (4). Die Verwendung der$O$Notation ist hier sehr schlampig, aber was ist hier gemeint, wenn man sagt, dass die Zeitkomplexität des Algorithmus ist$O(N^2)$ist, dass der Zeitaufwand in etwa proportional ist$N^2$. Das heißt, es gibt eine Konstante$k$so dass die Zeit, die zum Verarbeiten einer Eingabegröße erforderlich ist$N$ist circa$kN^2$. In diesem Problem wird Ihnen gesagt, wann$N=1000$, es ist ____ Uhr$10$Sekunden, also$k(1000)^2=10$. Das könntest du lösen$k$, wenn du wirklich wolltest, aber es ist unnötig: du willst$kN^2$Wenn$N=1,000,000$, Und$1,000,000=1000^2$, also du möchtest

$$k(1,000,000)^2= k(1000)^2(1000)^2=10(1000)^2=10,000,000\;,$$ seit $k(1000)^2=10$. Mit anderen Worten, in (4) benötigt Ihr Algorithmus etwa zehn Millionen Sekunden, was etwas weniger als einem Drittel eines Jahres entspricht.

In (2) wird Ihnen gesagt, dass der Algorithmus ungefähr dauert$kN$Sekunden, um ein Größenproblem zu lösen$N$, und du weißt das$1000k=10$. Ich lasse Sie versuchen, dieses Problem zu lösen und (5) meine Lösung für (4) als Modell zu verwenden; Sie sollten etwas mehr als zweidreiviertel Stunden für (2) und mehr als drei Jahrhunderte für (5) bekommen.

Schauen wir uns nun (1) an: Es besagt, dass die ungefähre Laufzeit bei einer Eingabe von size$N$Ist$k\log N$für einige konstant$k$, und das wird uns gesagt$k\log 1000=10$. Die Annäherung ist erlaubt$\log 1000\approx 10$, also haben wir$10k=10$, oder$k=1$. Somit ist die ungefähre Laufzeit z$N=1,000,000$Ist

$$k\log 1,000,000=\log 1,000,000\approx 20$$ Sekunden.

(3) sieht am chaotischsten aus, ist aber nicht schwieriger als die anderen: die ungefähre Laufzeit bei einer Größeneingabe$N$Ist$kN\log N$, und das ist dir gegeben$k(1000)\log 1000=10$. Auch hier können Sie entweder nach lösen$k$und einstecken$N=1,000,000$oder den angegebenen Datenpunkt direkter verwenden, wie ich es bei (4) getan habe; Sie sollten eine Laufzeit von etwas mehr als fünfeinhalb Stunden erreichen.