Я пытаюсь решить эту повторяемость
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)?
Это объяснит ситуацию лучше
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).
n lg3 не O (n). Он перерастает O (n)... Фактически, любой показатель степени на n, больший 1, приводит к асимптотически большему времени, чем O (n). Поскольку lg (3) составляет около 1,58, до тех пор, пока вы вычитаете меньше 0,58 от экспоненты, оно асимптотически больше O (n).