While(n>=1)
{
n=n/20;
n=n/6;
n=10×n;
n=n-10000;
}
ich versucht, ähnliche =>Was ist die zeitliche Komplexität des gegebenen Codes?
In dieser Schleife wird N durch N reduziert/12 - 10000. so, Zeitkomplexität O (log N) ist.
Das scheint richtig zu sein. Wenn dies eine Übung ist, sollten Sie bereit sein zu argumentieren, warum O(log_12(N))O(log(N)) ist.
Basen von Logarithmen sind in der Reihenfolge des Wachstums immateriell : Logarithmen zu verschiedenen Basen unterscheiden sich durch konstante Faktoren – Garrick
Ja, aber können Sie das mathematisch beweisen? – mort
Ich weiß nicht, wo ich falsch liege, aber warum ist es nicht 'O (log (N + konstant)) '? – YiFei
Wenn Sie eine Idee über die Komplexität haben, können Sie konkrete Werte für einige n berechnen und den resultierenden Graphen mit der angenommenen Komplexität vergleichen. Wenn beide Diagramme ähnlich sind, können Sie einen Beweis dafür finden, warum Ihre Annahme richtig ist. – MrSmith42
danke! Ich werde das im Hinterkopf behalten – Garrick
Bitte posten Sie nicht, was im Grunde die gleiche Frage alle paar Stunden ist (http://stackoverflow.com/questions/39324836/what-is-the-time-complexity-of-given-code) . Vielleicht möchten Sie zuerst eine allgemeinere Q & A lesen, wie: http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm – m69