Die Frage wird mit der Absicht gestellt,/lassen zu verstehen, wie man überprüft Asymptotic Θ Notation. Eine Hausaufgabenfrage. Ich bin zu zeigen, dass n (0)Ist n ≠ Θ (logn)?
Lösung: Ja, n ≠ Θ (logn).
c1logn ≤ n ≤ c2logn => c2≥n/logn, Ɐ n≥n0 - Impossible
Warum c2≥n/logn ist nicht möglich?
Denken Sie darüber nach, c2 ist eine Konstante, wenn Ihr n groß wird, um welchen Wert wird n/log (n) konvergieren?
Danke, verstanden es. –
Nun,
f(n) = Θ(g(n))
, wenn und nur wenn es eine endliche Grenzwert
lim f(n)/g(n) = c > 0
n -> +inf
was bedeutet, dass für alle Konstanten c1 < c < c2 wir n0 so dass f(n)/g(n) wird im [c1..c2] Bereich finden können, alle n > n0 (anders ausgedrückt c1*g(n) < f(n) < c2*g(n) wenn n > n0). In Ihrem Fall
f(n) = n
g(n) = log(n)
Die Grenze (wir verwenden L'Hôpital's rule)
lim n/log(n) = lim 1/(1/n) = lim n = +inf
n -> +inf n -> +inf n -> +inf
nein es ist so ein endliche Konstante c (und wir können nicht wählen Sie eine beliebige c2 konstant, so dass c < c2) ist.
Tolle Erklärung !! Ich habe nie so gedacht. –
einfach,
c2 will always be less than n für jeden Wert von n, die hier einen Widerspruch verursacht. Und so ist c2 ≥ n/logn nie möglich.
Ich stimme für das Schließen dieser Frage als Off-Topic ab, weil es sich um [cs.se] oder [math.se] handelt. – Dukeling
@Dueling wenn du sagst Off-topic, was meinst du damit? –
Von ["off-topic"] (https://stackoverflow.com/help/on-topic) Ich meine die Frage ist unpassend für [so] und wäre besser für eine andere Seite geeignet. Aber [poste es nicht auf mehreren Seiten] (https://meta.stackexchange.com/questions/64068/is-cross-posting-a-question-on-multiple-stack-exchange-sites-permitted-if- the-qu), und wahrscheinlich nicht (löschen und) reask oder migrieren Sie es, wenn Sie bereits eine befriedigende Antwort erhalten haben, es sei denn, Sie glauben, dass die Frage viel zukünftigen Wert für andere haben könnte. Einige Zeitkomplexitätsfragen sind Thema, aber dieses hier ist etwas zu mathe-schwer und Code-Licht für hier. – Dukeling