n log n равно O (n)?

Я пытаюсь решить это повторение

T(n) = 3 T(n/2) + n lg n ..

Я пришел к решению, что оно относится к случаю 2 теоремы мастеров, поскольку n lg n равно O (n ^ 2)

но после обращения к руководству по решению я заметил это решение, которое у них есть

введите здесь описание изображения

Решение говорит, что n lg n = O ( n ^ (lg 3 - e)) для e между 0 и 0,58.

так что это означает, что n lg n равно O (n) .. это правильно? Я что-то упустил здесь?

Разве nlgn не O(n^2)?


recurrence algorithm
person Wael Awada    schedule 20.10.2011    source источник

Ответы (3)


arrow_upward
88
arrow_downward

Это лучше объяснит ситуацию введите здесь описание изображения

person Sreenath Nannat    schedule 20.10.2011
comment
спасибо за усилия .. Так что я думаю n lg n › O(n) .. и книга неверна? - person Wael Awada; 20.10.2011
comment
@WaelAwada Ответ книги не противоречит O (n log n) › O (n). - person Ilian; 20.10.2011
comment
@WaelAwada Выдержка из книги выглядит в письменной форме (если не повезло поменять местами первый и второй термин) для: У нас есть два термина, которые следует учитывать для определения простых доминирующих функций: n lg n и n^logb a. Поскольку в n lg n доминирует n в степени всего больше единицы, над ним доминирует n^lg 3< /я>. - person greybeard; 14.11.2014
comment
Вы взяли эту схему отсюда? bigocheatsheet.com Вы должны указать свой источник! - person Lukas Eder; 12.05.2016
comment
Фиолетовая линия этого графика для O(nlogn) неверна. Посмотрите на 100 на оси x. Он должен отображаться как 100 * log (100) = 100 * 2 = 200. Вместо этого на диаграмме он отображается примерно как 650. Возможно, они добавили постоянный множитель, но не сделали этого для других линий. Странный. - person Anssssss; 07.03.2017
comment
Это Log2 (100) ~ 7 - person cognacc; 14.04.2017

arrow_upward
14
arrow_downward

n*log(n) не O(n^2). Он известен как квазилинейный и растет намного медленнее, чем O(n^2). На самом деле n*log(n) меньше полинома.

Другими словами:

O(n*log(n)) < O(n^k)

где k > 1

В вашем примере:

3*T(2n) -> O(n^1.585)

Поскольку O(n^1.585) является полиномиальным и доминирует над O(n*log(n)), последний член уменьшается, поэтому окончательная сложность составляет всего O(n^1.585).

person Mysticial    schedule 20.10.2011
comment
Я думал, что последний термин падает только тогда, когда он является сложением.. так что O (n + lg n) = O (n) - person Wael Awada; 20.10.2011
comment
И в этом случае тоже падает. Но потребуется полный пример/анализ, чтобы показать, почему. - person Mysticial; 20.10.2011

arrow_upward
6
arrow_downward

nlg3 не равно O(n). Он перерастает O (n) ... Фактически, любой показатель степени n, превышающий 1, приводит к асимптотически большему времени, чем O (n). Поскольку lg(3) составляет около 1,58, если вы вычтете из показателя степени менее 0,58, оно будет асимптотически больше, чем O(n).

person Community    schedule 20.10.2011
comment
Итак, если я правильно понимаю, вы, как и я, думаете, что руководство по решению неверно, говоря, что n lgn = O (n) - person Wael Awada; 20.10.2011
comment
Нет! n log n больше, перерастает и НЕ ограничено n. Все наоборот. - person ; 20.10.2011
comment
f(n) = O(g(n)) если f(n) ‹ c.g(n) для всех n › n0 .. поэтому, если n lg n = O(n), какими будут c и n0? - person Wael Awada; 20.10.2011
comment
Пусть c = 1, а n0 равно 5, и вы увидите, что это НЕВЕРНО. Наоборот. - person ; 20.10.2011
comment
так что если наоборот, то n = O (n lg n), что я понимаю, но в книге говорится n lgn = O (n) - person Wael Awada; 20.10.2011