依赖嵌套的运行时分析

Question

0

这里是算法：

int sum = 0
for (int i = 2N; i > 0; i = i / 4) 
  for (int j = 0; j < i; j+=2) 
    sum++
  end for
end for

我认为这是线性的，但只是线性的。我希望看到正式的总结而不是定性的解释。我已经尝试过这样做，但是我无法获得线性运行时。

Answer 1

在第一次外部迭代中，总和增加约N次，在第二次-大约N / 4次，然后大约N / 16次，依此类推。因此总数大约N + N / 4 + N / 16 + N / 64 + ...，相当于4N / 3。

您可以以更正式的方式轻松地证明它，但是对于SO社区而言，这将是没用的。因此，您的复杂度只是线性的。

Answer 2

切成小块：

int sum = 0

这里有O（1）。

for (int i = 2N; i > 0; i = i / 4) 

这将运行多少次？假设它将运行k次并评估k：

2N / 4 ^ k = 1 => 2N = 4 ^ k => k = log4（2N）。为简化起见，我们仅调用k = lg（N）。

for (int j = 0; j < i; j+=2) 
    sum++
end for

在第一种情况下，此运算直到N，然后是N / 4，然后是N / 16，等等。>>

这给您的是：

∑（N / 4 ^ i），i = 0 ... k =

N * ∑ 1/4 ^ i，i = 0 ... k

∑ 1/4 ^ i，i = 0 ... k是小于4/3的级数，因为它停在k = lg（n），因为外循环只运行lg（n）次。 >

因此，复杂度为O（X <4/3 * N），因此是线性的。