2016-09-12 6 views
0

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

+1

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

Antwort

1

Ihre aktuelle Laufzeit ist falsch. Da Sie immer alle Werte i und j durchlaufen, dauert es insgesamt 100*2000 Iterationen. Dies ist unabhängig von Ihrem n Wert. Wenn Sie jedoch annehmen, dass Ihre Unbekannten die Werte i und j sind, die durch I bzw. J gekennzeichnet sind, können Sie sagen, dass Ihr Algorithmus die Laufzeit O(IJ) hat. Sie sind auf der richtigen Spur, ersetzen Sie einfach Ihre Konstanten für Variablen.

+0

Vielen Dank .. Gut erklärt :) – Kris

+0

Ich entschuldige mich für die Rückkehr wieder. Jetzt verstehe ich, dass die Laufzeit für meinen obigen Algorithmus unabhängig von n ist, d.h. für jede Eingabegröße "100 * 2000" benötigt. Also, wie stelle ich das dar, ist Big-Oh-Notation? Ist es akzeptabel, "O (100 * 2000)" zu sagen? – Kris

+0

Ihr Algorithmus ist konstant in Bezug auf 'n', also würden Sie' O (1) 'sagen. Ich habe das Big-O für das Szenario gegeben, in dem du "I" und "J" variiert hast. – CoconutBandit

Verwandte Themen