内部ループを持つアルゴリズムの最悪の場合の時間複雑度はどのようにして見つけられますか？ [duplicate] - アルゴリズム、時間複雑さ

2つのforループを持つコードがあるとします。

int sum = 0;
for (int i = 1; i < N; i *= 2)
for(int j = 0; j < i; j++)
sum++;

最悪の場合の時間計算量をどのように見つけますかこのコードの？私は時間計算量を見つけるための多くのチュートリアルを見て、それらを理解しました。しかし、これはチュートリアルのものとは少し異なっているように見えます。

回答：

簡単な計算をしましょう。 の値 i 各反復で次のようになります 1,2,4,8... (log N + 1) terms。各反復で、内側のループが進みます i 回。の値を合計する i

T（N）= 1 + 2 + ... +（log N + 1）項、つまりGPと a = 1 そして r = 2 そして n = (log N + 1)

T（N）= a [（rⁿ-1）/（r-1）]
= 1 [（2^{（logN + 1）} -1）/（2-1）]
= 2N-1
= O（N）

したがって、すべてのシナリオで複雑さはO（N）です。

最初に、より単純なケースを検討します。 N=2^k+1 いくつかの整数の場合 k。この場合、外側のループには k 反復と操作の総数は

 T(N) = 1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1 = 2N - 3.

したがって、最悪の場合の複雑さは少なくとも O(2N - 3) = O(N).

今仮定すると 2^k + 1 < N <= 2^(k+1) いくつかのための k。その後、

 T(N) = 1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1 < 2N = O(N)

したがって、 T(N) = O(N).