java - このアルゴリズムが線形であり、線形ではないのはなぜですか?

Question

int sum = 0; 
for (int n = N; n > 0; n /= 2)
   for (int i = 0; i < n; i++)
      sum++; 

nlognで成長すると確信していましたが、線形であると言われました...なぜ線形であり、線形ではないのですか?

Answer 1

線形です。1 秒が 64 であると想像してくださいn。内側のループは 64 回、次に 32 回、次に 16 回、次に 8 回、次に 4 回、次に 2 回、次に 1 回実行されます。64 + 32 + 16 + 8 + 4 + 2 + 1 = 127.

したがって、内側のループが最適化されていないと仮定すると、合計操作が必要になり2n-1ます (2 の累乗ですが、分析は変わりません)。それは明らかにO(n)直線的です。

内側の for ループが ( にsum += n;) 最適化されている場合、それは対数的です。

Answer 2

このアルゴリズムの複雑さは Θ(N) です。

操作回数は

sum{2**k} for k = 0..log2(N)

この進行の合計は

2*N-1

これは Θ(N) です。