Was ist schneller, einen Algorithmus mit einer Laufzeit von O (log n) einmal auf einer Eingabe der Größe 10n laufen zu lassen oder ihn zehnmal bei Eingaben der Größe n auszuführen?O (log 10n) oder O (log n) x 10 schneller?
O (log 10n) weil die logarithmische Zeit viel langsamer als die lineare Zeit ansteigt. Sie können es selbst zählen, z.
For n = 1000: log n = 10, 10 log n = 100, log 10n = 13
Wenn Sie überprüfen möchten, können Sie Limit-Test durchführen. lim (log(10n)/log(n)), n->infinity. (wolfram alpha)
wenn log(10n) ist 10-mal schneller als log(n), sollte es bis 10. konvergiert
log(10n)/log(n) = log_n(10n) = log_n(10) + 1. also, wenn n ins Unendliche geht, konvergiert log_n(10) gegen 0. (Sie können es überprüfen, indem Sie einige Log-Graphen überprüfen)
ist nicht die höhere die Zahl, desto schneller? also sollte nicht 10 log n schneller sein? – Naomi
@Naomi Say Einzeloperation braucht Zeit T. Logarithmische Komplexität bedeutet, dass diese Operation log n mal ausgeführt wird (basierend auf der Eingabe). Da log n sehr langsam ansteigt, bedeutet dies, dass mit Eingabe n = 1000 10 mal ausgeführt wird, so dass die benötigte Zeit 10T beträgt. Mit Eingabe 10n (10 000) wird es 13 mal ausgeführt, also wird die Zeit 13T sein. Auf der anderen Seite, wenn Sie 10 Mal n (1000) loggen würden, müsste es 100 (10 x log n oder 10 x 10) mal ausführen, also dauert es 100T. – Resurrection
n = 1000 log (n) = log (1,000) = 4 log (10N) = log (10000) = 5 10log (1000) = 10 (4) = 40 so log10n schneller sein würde als 10logn weil es wird T = 5 und nicht T = 40 oder? – Naomi