1

アルゴリズムの教科書の問題です。時間計算量はlog（n！）だと思いますが、クラスメートはnlog（n）だと言っています。お返事ありがとうございます!!

count ← 0
for i ← 1 to n do
    j ← ⌊n/2⌋
    while j ≥ 1 do
        count ← count + 1
        if j is odd then
           j←0
        else
           j ← j/2
        end if
    end while
 end for
4

2 に答える 2

3

時間計算量はだと思いますlog(n!)が、クラスメートはそう言っていますnlog(n)。

あなたは両方とも正しいです。スターリングの公式からわかるように、

log n! = n * log n - n +O(log(n)),

（logここでは自然対数です）より正確には：

log n! = (n + 1/2) * log n - n + 1/2 * log (2π) + O(1/n)

そうO(log n!)とO(n*log n)同じクラスです。

于 2013-03-14T16:54:41.500 に答える
1

最悪の場合、n = 2 p

  • ループ1からn
  • ループごとに、jを1未満になるまで2で割ります

したがって、n * log2(n)回の反復、または時間計算量O(n log(n))

-

（コメントによると、log 2（x）は実際にはlog（x）/ log（2） 、つまりlog（x）に定数を掛けたものであるため、複雑さにおいて対数ベースは必要ありません）

于 2013-03-14T16:16:30.377 に答える