Little-oh Notation im Detail, CS-Hausaufgaben ohne tatsächliche Zuordnung

Question

Ich sitze hier mit dieser Aufgabe in einem Kurs über Algorithmen mit massiven Datensätzen, und die Verwendung von Little-oh Notation hat mich verwirrt, obwohl ich mit Big-oh vollkommen zuversichtlich bin.

Ich möchte keine Lösung für die Aufgabe, und als solches werde ich sie nicht präsentieren. Stattdessen ist meine Frage, wie ich die Zeitkomplexität interpretiere o (log n)?

Ich weiß aus der Definition, dass ein Algorithmus A asymptotisch langsamer wachsen muss als O (log n), aber ich bin mir nicht sicher, ob dies bedeutet, dass der Algorithmus in konstanter Zeit laufen muss oder ob es noch sein darf sein dürfen Protokoll n unter bestimmten Bedingungen, so dass c = 1 oder wenn es wirklich ist log (n-1).

Sagen Sie, ein Algorithmus hat eine Laufzeit von O (log n) aber tatsächlich macht zwei Iterationen und als solche c = 2, aber aber 2*log n ist immer noch O (log n), Habe ich Recht, wenn ich sage, dass dies nicht für Little-oh gilt?

Jede Hilfe wird sehr geschätzt, und wenn ich ausschließlich zur Klärung benötigt wird, werde ich die Aufgabe anbieten

Answer 1

Zu sagen f ist 'Little-oh-of G' f = o(g), bedeutet, dass der Quotient

|f(x)/g(x)|

nähert sich 0 als x nähert sich unendlich. Beziehen Sie sich auf Ihr Beispiel von o(log n), diese Klasse enthält Funktionen wie log x / log (log x), sqrt(log x) und noch viel mehr, also o(log x) definitiv nicht impliziert O(1). Auf der anderen Seite, log (x/2) = log x - log 2, Also

log (x/2) / log x = 1 - log 2 / log x -> 1

und log (x/2) ist nicht in der Klasse o(log x).

Answer 2

Für Little-OH muss F (x) für alle x nicht kleiner als g (x) sein. Es muss erst nach einem bestimmten Wert von x kleiner sein. (Für Ihre Frage darf es unter bestimmten Bedingungen immer noch log n sein.)

Zum Beispiel:

 let f(x) = 5000x and g(x) = x^2

f (x) / g (x), wenn x sich unendlich nähert, beträgt 0, also ist f (x) ein wenig-o von g (x). Bei x = 1 ist F (x) jedoch größer als g (x). Erst nachdem x größer als 5000 wird g (x) größer als F (x).

Was Little-O uns wirklich sagt, ist, dass G (x) immer schneller wächst als F (x). Schauen Sie sich beispielsweise an, wie viel f (x) zwischen x = 1 und x = 2 gewachsen ist:

 f(1) = 5000
 f(2) = 10000 - f(x) became twice as big

Schauen Sie sich nun G (x) im gleichen Intervall an:

 g(1) = 1
 g(2) = 4 - g(x) became four times bigger

Diese Rate wird bei größeren Werten von x noch stärker zunehmen. Da G (x) schneller ansteigt und wir X in die Unendlichkeit bringen, wird es irgendwann größer als F (x). Aber das ist nicht das, womit sich Little-O befasst, es geht nur um die Änderungsrate.