Ist f (n) = 1000n + 4500lgn + 54n O (n)?

Question

war ich die folgende Frage in meinem Test gegeben:

Ist f (n) = 1000n + 4500lgn + 54n O (n)?

ich diese Frage zu beantworten, indem die folgende Definition Anwendung:

Definition von O (n), die es sein, dass für eine Funktion f (n) müssen zwei positive Konstanten sind, C und K, so dass c> 0, k> 0, n> = k und 0 < = f (n) < = cn. Wenn wir zeigen können, dass die Konstanten c und k existieren, dann ist die Funktion O (n) (und wenn diese Konstanten nicht existieren, dann ist die Funktion tatsächlich größer als O (n)).

Lösung:

0 ≤ 1000N + 4500lgn + 54n ≤ cn
0 ≤ 4000 + 9000 + 216 ≤ 4c, wenn k = 4
0 ≤ 3304 ≤ c

0 ≤ 8000 + 13500 + 432 ≤ 8n wenn n = 8> k
0 ≤ 21932 ≤ 8n
0 ≤ 2741.5 ≤ n (letztes mal c = 3304 aber jetzt ist es 2741.5 .... wie n zunimmt, c ist nicht konstant!)

Fazit:
Diese Funktion ist nicht O (n) - wir können die konstanten Werte c und k nicht finden, weil sie einfach nicht existieren.

Ist meine Lösung korrekt?

Answer 1

0 ≤ 2741,5 ≤ n (letztes Mal c = 3304, aber jetzt ist es 2741,5 .... wenn n zunimmt, c nicht konstant ist!)

Der Fehler in Ihrer Lösung ist, dass wenn Sie bleiben mit dem ursprünglichen Wert von c, die Einschränkung ist immer noch zufrieden. Es ist nicht der tatsächliche Wert der Konstanten, auf den es ankommt, einfach, dass es ein Paar von Konstanten c und k gibt, für die die Ungleichheit erfüllt ist für alle n > k.

Ich weiß nicht, welches Maß an Strenge (von Ihren Lehrern) in einer Antwort auf diese Frage erforderlich ist. Eine rigorose Lösung würde jedoch einen mathematischen Beweis erfordern (nach ersten Prinzipien oder etablierten Theoremen), dass entweder c und k existieren oder dass sie nicht existieren können.

---

^{1 - Ein Paar c und k, die Sie nachweisen kann die Einschränkung für alleN > k nicht erfüllt wäre ein ausreichender Beweis sein.}

Answer 2

_{log 2 n} < n, so 1000N + 4500 log 2 n + 54n ≤ 1000N 4500N + + 54n.

Addieren Sie einfach die Koeffizienten.Für k = 1 und c = 1000 + 4500 + 54 = 5554, f(n) ≤ c*n für alle n ≥ k. Daher ist fO(n).