как показать, что 5n = O (nlogn)

Question

У меня это как домашний вопрос, и я не помню, чтобы изучал его в классе. Может кто-то указать мне правильное направление или иметь документацию о том, как решить эти типы проблем?

Answer 1

Более формально ...

Сначала докажем, что если f(n) = 5n, то f ∈ O(n).Чтобы показать это, мы должны показать, что для некоторых достаточно больших k и i ≥ k, f(i) ≤ ci.К счастью, c = 5 делает это тривиальным.

Далее я докажу, что для всех f ∈ O(n) это f ∈ O(n * log n).Следовательно, мы должны показать, что для некоторых достаточно больших k все i ≥ k, f(i) ≤ ci * log i.Следовательно, если мы позволим k быть достаточно большим, чтобы f(i) ≤ ci и i ≥ 2, то результат будет тривиальным, поскольку ci ≤ ci * log i.

QED.

Answer 2

Посмотрите на определение big-O-обозначения. Это означает, что 5n будет работать не медленнее nlogn, что верно. nlogn - это верхняя граница количества выполняемых операций.

Answer 3

Вы можете доказать это, применив правило L'Hopitals к lim n-> бесконечности 5n / nlogn

g (n) = 5n и f (n) = nlogn

Производные g(n) и f (n), так что вы получите что-то вроде этого

5 / (некоторые вещи здесь, которые будут содержать n)

5 / infinity = 0, поэтому 5n = O (nlogn)верно

Answer 4

Прошло три года с тех пор, как я коснулся Big-O. Но я думаю, что вы можете попытаться показать это:

O (5n) = O (n) = O (nlogn)

O (5n) = O (n) очень легко показать, поэтому все, что вам нужно сделать сейчас, это показать O (n) = O (nlogn), что тоже не должно быть слишком сложно

Answer 5

Я не помню формулировку формального определения, но вы должны показать:

c ₁ * 5 * n 2 * n * logn, n> c ₃

, где c ₁ и c ₂ - произвольные постоянные, для некоторого числа c ₃ .Определите c ₃ в терминах c ₁ и c ₂ , и все готово.