最悪の場合に発生するアルゴリズムを分析しようとしています
log(1) + log(2) + log(4) + log(n_i) + ... + log(log(n))
仕事量。n_i は 2 の累乗です。
私の試みは、次のように言うことです：
1 + 2 + 3 + ... + n
は O(n^2)、私のアルゴリズムは O(log(n^2)) = O(2log(n)) です。
これは正しいです？
さらに、各 log(n_i) 項が独立した確率 0.5 で発生することだけを期待します。では、上記の予想される複雑さは O(2log(n)/2) = O(log(n))であると主張できますか?
ポンド(1) + ポンド(2) + ポンド(4) + ... + ポンド(ポンド(n))
= lb(2 0 ) + lb(2 1 ) + lb(2 2 ) + ... + lb(2 lb(lb(n)) )
= 0 + 1 + 2 + ... + ポンド(ポンド(n))
= O([ポンド(ポンド(n))] 2 )
X(i) を i 番目の項を表す確率変数とします。ここで、X(i) = lb(2 i ) = i の確率は 1/2 で、それ以外の場合は X(i) = 0 です。次に、E[X(i)] = i/2 です。
したがって、X(0) + X(1) + ... + X(lb(lb(n))) の期待値は、期待値の直線性により、上記の決定論的な結果のちょうど 1/2 になります。つまり、予想される複雑さは依然として O([lb(lb(n))] 2 ) です。
log(x) = lb(x)/lb(e) および lb(e) は定数であるため、log (基数 e) と lb (基数 2) の区別は、漸近的な複雑さを扱う場合には無関係であることに注意してください。