Ist die Quadratwurzel von n näher an O (log n) oder O (n)?

Question

Ich habe zwei Algorithmen A und B.

Zeitkomplexität von Algorithmus A ist O (log n ) und der von B ist O (n).

Jetzt habe ich einen neuen Algorithmus C, die Zeitkomplexität von O (√ n) Ich muss beweisen (mathematisch), ob Algorithmus A oder B-Algorithmus hat asymptotisch näher C.

Beliebig Algorithmus Hilfe dabei ist sehr geschätzt. Vielen Dank!

Answer 1

Ist die Quadratwurzel von n näher an O (logn) oder O (n)?

(ich bin im folgenden davon aus, dass Sie tatsächlich bedeuten Θ, nicht O (Danke für den Hinweis, dass out). Andernfalls WhatsUp, das ist nur obere Grenzen, und man kann nicht sagen etwas über die Unterschiede der von oberen Grenzen beschränkten Funktionen.)

ersten Start mit dem spezifischen Funktionen log Lassen Sie uns (n), √ n und n. Offensichtlich log (n) ≤ √ n ≤ n (Sie können die L'Hospital-Regel verwenden, um dies zu sehen). Also die Frage ist, wenn n - √ n ist größer oder weniger als √ n - log (n).

Anwenden von L'Hospital Regel

lim _{n → ∞} (n - √ n)/(√ n - log (n)),

Sie können sehen, dass diese

ist

lim _{n → ∞} (1 - 0,5/√ n)/(0,5/√ n - 1/n) = lim _{n → ∞} (n - 0,5 √ n)/(0,5 √ n - 1) = lim _{n → ∞} (n - 0,5 √ n)/(0,5 √ n) = ∞.

So ist √ n näher an log (n) als zu n.

---

Mit Θ die Berechnungen sind im Wesentlichen die gleichen, aber langweiliger. Sie müssen argumentieren, dass jede Funktion zwischen zwei Konstanten beschränkt ist, und verwenden Sie die oberen und unteren entsprechend. Ungeachtet, kategorisch, wenn f, g und h sind Θ (log (n)), Θ (√ n) und Θ (n), dann groß genug n, g (n) - f (n) < < h (n) - g (n).