Сложность времени и вопрос, связанный с обозначениями Big-O - PullRequest
Новая
       3

Сложность времени и вопрос, связанный с обозначениями Big-O

3 голосов
/ 23 июня 2011

Вопрос в одном из моих прошлых экзаменов - это вопрос с несколькими вариантами ответа: 

Choose the FALSE statement: 7(log n) + 5n + n(log log n) + 3n(ln n) is

A. O(n^2)
B. Ω(n^2)
C. O(n log^2 n)
D. Ω(n)
E. Θ(n log n)

Сначала я пришел к выводу, что время выполнения алгоритма должно быть Θ (n log n), что исключаловариант E. Затем я пришел к выводу, что вариант B, Ω (n ^ 2), ложь, потому что я знал, что Θ (n log n) меньше, чем Θ (n ^ 2), поэтому Ω (n ^ 2) не может бытьправда.Поэтому я подумал, что ответом будет B.

Но я также понял, что C также не может быть правдой, поскольку Θ (n log n) больше времени выполнения, чем Θ (n log ^ 2 n).Но это не может быть 2 из правильных ответов.

Так что правильно: это B?или это С?или нет?Я весьма озадачен.: S

Ответы [ 2 ]

3 голосов
/ 23 июня 2011

ложное утверждение omega(n^2).
это точно theta(nlogn) (так как 3n (ln n)) является "самым высоким", и это theta(nlogn).
omega(n^2) говорит, что это не лучше, чем n ^ 2 сложность, что здесь неверно.


сложение: в вашем примере верно следующее:
7 (log n)
7logn = тета (logn), 5n = тета (n), n (loglogn) = тета (nloglog (n)), 3nln (n) = тета (nlogn)
который, как сказано, (nlogn) является высшим, таким образом:
7(log n) + 5n + n(log log n) + 3n(ln n) = theta(nlogn)
и все - o (n ^ 2) (здесь специально обозначено маленькое o), поэтому Омега (n ^ 2) - ложное утверждение.

РЕДАКТИРОВАТЬ: уточнения и добавления того, что я написал в комментариях:
опция C имеет значение True, потому что O (nlogn) nlog^2(n) = n*log(n)*log(n) > n*log(n) для каждого n> 2.
пример: для n = 1 000 000: nlogn = 1,000,000*20 = 20,000,000
, а n*log^2(n) = 1,000,000*20*20=400,000,000.

1 голос
/ 23 июня 2011

Предполагая, что log - это логарифм основания 2, а ln - натуральный логарифм, верно следующее утверждение:

Θ (журнал ( N )) <Θ (<em> N · журнал (журнал ( N ))) <Θ (<em> п ) <Θ (<em> п · п ( п )) * * 1016

Таким образом, общая сложность составляет Θ ( n · ln ( n )).

Теперь давайте проверим утверждения:

  • n · ln ( n ) ∈ O ( n 2 ) равно true

    n · ln ( n ) ≤ c · ‍ n 2 для c = 1, ‍∀ n ≥ 0

  • n · ln ( n ) ∈ Ω ( n 2 ) равно false

    n · ln ( n ) ≱ n 2 , следовательно, ln ( n ) <<em> c · * n * для c = 1, ‍∀ n ≥ 0

  • n · ln ( n ) ∈ O ( n · (log ( n )) 2 ) - true

    n · (журнал ( n )) 2 = n · (ln ( n ) / ln (2)) 2 = n · (ln ( n )) 2 / (ln (2)) 2 и n · ln ( n ) ≤ c · ‍ n · (ln ( n *) 1139 *)) 2 / (ln (2)) 2 для c = (ln (2)) 2 , ∀ n ≥ e

  • n · ln ( n ) ∈ Ω ( n ) равно true

    n · ln ( n ) ≥ c · ‍ n для c = 1, ∀ n ≥ 0

  • n · ln ( n ) ∈ Θ ( n · log ( n )) равно правда

    n · log ( n ) = n · ln ( n ) / ln (2) и n · ln ( n ) = c · ‍ n · ln ( n ) / ln (2) для c = ln (2), ∀ n ≥ 0

...