Сложность алгоритма, log^k n vs n log n

Question

Я разрабатываю некоторый алгоритм с учетом O (log^3 n). (ПРИМЕЧАНИЕ: возьмите O как большую тету, хотя Big O тоже будет хорошо)

Я не уверен, тогда как O (log^3 n) или даже O (log^2 n) считается более/менее/equy как O (n log n).

Если бы я следовал правилам, я бы сказал, что O (n log n) является более сложным, но, тем не менее, я не знаю, как и почему.

Я провел некоторое исследование, но я не смог найти ответ на этот вопрос.

спасибо.

Answer 1

Таким образом, (п § п) "больше", чем ((журнал N)). Это можно легко обобщить на ((log n) ^k) по индукции.

Answer 2

Если вы graph the two functions together вы можете увидеть, что п журнала (п) растет быстрее, чем войти н.

Чтобы доказать это, вы должны доказать, что п лог п> войти п для всех значений п больше некоторого произвольного числа с. Найдите такой c, и у вас есть доказательства.

Фактически, n log(n) grows faster than any log^xn для положительных x.