11

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)にも成長します。

4

3 に答える 3

4

nが十分に大きいので、次のn^(log(n))ように書くことができます。これは、k^nよりも遅くなることを意味します。(k^(logk(n)))^(log(n)) = k^(K*(log(n)^2)).(log(n))^2 < nn^(log(n))

于 2011-05-01T20:56:23.213 に答える
1

に置き換えnてみてください。b^mこれにより、が作成されますlogb(n) = m。それはあなたにどこへ行くべきかについての考えを得るはずです。

于 2011-05-01T20:56:10.050 に答える
1

theta(exponential)やtheta(polynomial)ではないようです。上のポスターは、指数関数的でない理由を示しています。多項式でない理由は、反例による簡単な証明でできます。

n^logn が O(n^k) でないことの証明:

  • n>n_0 の場合、c*n^k > n^log n となるようないくつかの c と n_0 を持ついくつかの k があるとします。これが O(n^k) の定義です。
  • これが成り立たないように、定数を使用して を見つけるのは簡単です。
  • c>1 の場合、その n は (ck)^ck です。
  • c<1 の場合、その n は k^k です。
于 2012-04-27T05:09:19.047 に答える