f (n) = n ^ log (n) полиномиальная или экспоненциальная сложность

Question

Я пытаюсь выяснить, находится ли f(n)=n^(logb(n)) в Theta(n^k) и, следовательно, становится полиномиальным или в Theta(k^n) и, следовательно, растет в геометрической прогрессии.

Сначала я попытался упростить функцию: f(n) = n^(logb(n)) = n^(log(n)/log(b)) = n^((1/log(b))*log(n)) и поскольку 1/log(b) является постоянным, мы получаем f(n)=n^log(n).

Но теперь я застрял. Я предполагаю, что f(n) растет экспоненциально в Theta(n^log(n)) или даже гипер экспоненциально, потому что показатель log(n) также растет.

Answer 1

Вы можете написать n^(log(n)) как (k^(logk(n)))^(log(n)) = k^(K*(log(n)^2)). Поскольку (log(n))^2 < n для n достаточно велико, то это означает, что n^(log(n)) будет расти медленнее, чем k ^ n

Answer 2

кажется, что это не тета (экспоненциальный) или тета (полином) ; постеры выше показали, почему это не экспоненциально. Причину, по которой он не является полиномиальным, можно сделать с помощью простого доказательства на контрпримере.

доказательство того, что n ^ logn не O (n ^ k):

• предположим, что существует некоторое k, с некоторыми c и n_0, такими, что для n> n_0 c * n ^ k> n ^ log n. это определение O (n ^ k).
• просто найти n с постоянными, чтобы это не выполнялось.
• если c> 1, то это n (ck) ^ ck.
• если c <1, то это n равно k ^ k. </li>

Answer 3

Попробуйте заменить n на b^m, что составляет logb(n) = m. Это должно дать вам представление о том, куда идти.