Ich lerne, wie der Algorithmus (Erste 5 Kapitel) von mir selbst zu analysieren, mit diesem Buch: Introduction of Algorithms. Angenommen, ich habe den folgenden einfachen Algorithmus (Ich habe es nach oben):So schätzen Sie die Laufzeit, wenn die Eingangsgröße unbekannt ist
for i <- 0 to 100
for j <- 1 to 2000
if (i*10 + j*20 = n)
c <- c+1
Nun, wenn ich die Laufzeit dieses Algorithmus für eine spezifische Eingangsgröße schätzen will, sagen n= 500
, würde ich sagen:
Die Laufzeit im schlimmsten Fall ist T(n) = 100*2000*500 = 10 * 10^7
. Wenn ich jedoch für jede Eingabegröße verallgemeinern möchte, d. H. n
, weiß ich nicht, wie das geht! Bitte, kann mich jemand aufklären?
Vielen Dank
Big-O verallgemeinert bereits über n als n -> unendlich. So wäre es zum Beispiel: "O (n * n) = O (n^2)" (ersetzt n für beide i und j, da sie unabhängig und nicht weiter qualifiziert sind). – user2864740