n log n это O (n)?

Question

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

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

Answer 1

Это объяснит лучше

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

Answer 3

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