Was bedeutet log O ( 1 ) n
Ich kenne die Big-O-Notation, aber diese Notation macht für mich keinen Sinn. Ich kann auch nichts darüber finden, weil eine Suchmaschine dies auf keinen Fall richtig interpretiert.
Für ein bisschen Kontext lautet der Satz, in dem ich ihn gefunden habe, "[...] wir rufen eine Funktion [effizient] auf, wenn sie O ( log n ) Leerzeichen und höchstens log O ( 1 ) n pro Element verwendet."
asymptotics
landau-notation
Oebele
quelle
quelle
Antworten:
Sie müssen das starke Gefühl, dass sich das " O " am falschen Ort befindet , für einen Moment ignorieren und trotzdem mit der Definition fortfahren. f ( n ) = log O ( 1 ) n bedeutet , daß es Konstanten existieren k und n 0 , so dass für alle n ≥ n 0 , f ( n ) ≤ log k ⋅ 1 n = log k n .O f(n)=logO(1)n k n0 n≥n0 f(n)≤logk⋅1n=logkn
Note that logknlogkn means (logn)k(logn)k . Functions of the form logO(1)nlogO(1)n are often called polylogarithmic and you might hear people say, "ff is polylog nn ."
You'll notice that it's easy to prove that 2n=O(n)2n=O(n) , since 2n≤kn2n≤kn for all n≥0n≥0 , where k=2k=2 . You might be wondering if 2logn=logO(1)n2logn=logO(1)n . The answer is yes since, for large enough nn , logn≥2logn≥2 , so 2logn≤log2n2logn≤log2n for large enough nn .
On a related note, you'll often see polynomials written as nO(1)nO(1) : same idea.
quelle
This is an abuse of notation that can be made sense of by the generally accepted placeholder convention: whenever you find a Landau term O(f)O(f) , replace it (in your mind, or on the paper) by an arbitrary function g∈O(f)g∈O(f) .
So if you find
f(n)=logO(1)nf(n)=logO(1)n
you are to read
f(n)=logg(n)nf(n)=logg(n)n for some g∈O(1).(1)g∈O(1).(1)
Note the difference from saying "loglog to the power of some constant": g=n↦1/ng=n↦1/n is a distinct possibility.
Warning: The author may be employing even more abuse of notation and want you to read
f(n)∈O(logg(n)n)f(n)∈O(logg(n)n) for some g∈O(1).(2)g∈O(1).(2)
Note the difference between (1) and (2); while it works out to define the same set of positive-valued functions here, this does not always work. Do not move OO around in expressions without care!
quelle
It means that the function grows at most as loglog to the power of some constant, i.e. log2(n)log2(n) or log5(n)log5(n) or log99999(n)log99999(n) ...
quelle
"At most logO(1)nlogO(1)n " means that there is a constant cc such that what is being measured is O(logcn)O(logcn) .
In a more general context, f(n)∈logO(1)nf(n)∈logO(1)n is equivalent to the statement that there exists (possibly negative) constants aa and bb such that f(n)∈O(logan)f(n)∈O(logan) and f(n)∈Ω(logbn)f(n)∈Ω(logbn) .
It is easy to overlook the Ω(logbn)Ω(logbn) lower bound. In a setting where that would matter (which would be very uncommon if you're exclusively interested in studying asymptotic growth), you shouldn't have complete confidence that the author actually meant the lower bound, and would have to rely on the context to make sure.
The literal meaning of the notation logO(1)nlogO(1)n is doing arithmetic on the family of functions, resulting in the family of all functions logg(n)nlogg(n)n , where g(n)∈O(1)g(n)∈O(1) . This works in pretty much the same as how multiplying O(g(n))O(g(n)) by h(n)h(n) results in O(g(n)h(n))O(g(n)h(n)) , except that you get a result that isn't expressed so simply.
Since the details of the lower bound are in probably unfamiliar territory, it's worth looking at some counterexamples. Recall that any g(n)∈O(1)g(n)∈O(1) is bounded in magnitude; that there is a constant cc such that for all sufficiently large nn , |g(n)|<c|g(n)|<c .
When looking at asymptotic growth, usually only the upper bound g(n)<cg(n)<c matters, since, e.g., you already know the function is positive. However, in full generality you have to pay attention to the lower bound g(n)>−cg(n)>−c .
This means, contrary to more typical uses of big-oh notation, functions that decrease too rapidly can fail to be in logO(1)nlogO(1)n ; for example,
1n=log−(logn)/(loglogn)n∉logO(1)n
A counterexample of a somewhat different sort is that −1∉logO(1)n−1∉logO(1)n .
quelle