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

Я пытаюсь решить эту повторяемость

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

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

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

enter image description here

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

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

Не nlgn O (n ^ 2)?

Ответы

Ответ 1

Это объяснит ситуацию лучше enter image description here

Ответ 2

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).

Ответ 3

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