f (n) = n^log (n) phức tạp đa thức hoặc mũ số

Question

Tôi đang cố gắng tìm ra liệu f(n)=n^(logb(n)) có ở trong Theta(n^k) và do đó phát triển đa thức hoặc trong Theta(k^n) và do đó tăng theo cấp số nhân.

Trước tiên, tôi đã cố gắng đơn giản hóa chức năng: f(n) = n^(logb(n)) = n^(log(n)/log(b)) = n^((1/log(b))*log(n)) và vì 1/log(b) là hằng số chúng tôi nhận được f(n)=n^log(n).

Nhưng bây giờ tôi bị kẹt. Đoán của tôi là f(n) tăng theo cấp số nhân trong Theta(n^log(n)) hoặc thậm chí siêu theo cấp số nhân bởi vì số mũ log(n) cũng đang tăng lên.

Answer 1

Hãy thử thay thế n bằng b^m, làm cho logb(n) = m. Điều đó sẽ giúp bạn có được một ý tưởng về nơi để đi.

Answer 2

Bạn có thể viết n^(log(n)) như (k^(logk(n)))^(log(n)) = k^(K*(log(n)^2)). Kể từ (log(n))^2 < n cho n đủ lớn, thì điều này có nghĩa là n^(log(n)) sẽ tăng trưởng chậm hơn so với k^n

Answer 3

nó có vẻ như nó không phải theta (mũ) hoặc theta (đa thức); các áp phích trên cho thấy lý do tại sao nó không phải là mũ. Lý do tại sao nó không phải là đa thức có thể được thực hiện với một bằng chứng đơn giản bằng ví dụ truy cập.

bằng chứng rằng n^logn không phải là O (n^k):

• giả sử có một số k, với một số c và n_0 như vậy mà cho n> n_0, c * n^k> n^log n. đây là định nghĩa của O (n^k).
• thật đơn giản để tìm một n, với các hằng số, sao cho nó không giữ.
• nếu c> 1, thì đó là n (ck)^ck.
• nếu c < 1, thì đó là k^k.