两个依赖for循环的复杂性，具有log n复杂性的外循环 [英] complexity of two dependent for loops with outer loop of log n complexity

问题描述

问题

计算此算法的复杂性：

 for(i=n; i>1;i=i/2)
   for(j=i;j<n;j++){
         statement;
   }

我之前在这个主题上做了什么：

第一个循环运行登录时间。
第二个循环运行n-i次，i从n开始，并在每个外循环迭代中更改为i / 2。所以内部循环运行如下：

The first loop runs logn times. The second loop runs n-i times with i starting from n and changing to i/2 in each outer loop iteration. So the inner loop runs like this:

n-n                             0 times

n - n/2                        n/2 times

n - n/4                        3n/4 times

n - n/8                        7n/8 times

n - n/16                     15n/16 times

依此类推

n - 1 次

所以一般术语是 n *（（2 ^ n）-1 ）/（2 ^ n）

现在这个序列不是算术的，也不是几何的。因此无法在其上应用 n / 2 *（a + l）的公式。如何进一步处理此解决方案或者如果错误，那么正确的方法是什么。

Now this sequence is not arithmetic nor geometric. So formula of n/2 * (a+l) cannot be applied on it. How do I further proceed with this solution or if it is wrong, then what is the correct method.

注意：如果 n / 2 *（应用a + l），结果复杂度为 -n /（2 ^ n）= O（2 ^ n）。

Note: If n/2*(a+l) is applied, the resulting complexity is -n/(2^n) = O(2^n).

推荐答案

你走在正确的轨道上。正如您所提到的，内部循环将运行 log n 次。因此，它运行的总次数是：

You are on the right track. As you mentioned, the inner loop would run log n times. So, the total number of times it runs is:

    (n - n/2) + (n - n/4) + ... (log n) times
  = n*(log n) - (n/2 + n/4 + n/8 + ... up to 1)
  = n*(log n) - n*(1/2 + 1/4 + ...)
 <= n*(log n) - n because (1/2 + 1/4 + ...) is 1 even if we take all terms till infinity (G.P)
  = n(log n - 1), which is O(n*log(n))

请记住，在计算复杂性时，您总是在寻找上限，而不是确切的数字。

Remember that when calculating complexity, you are always looking for upper bounds, not exact numbers.

这篇关于两个依赖for循环的复杂性，具有log n复杂性的外循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！