两个复杂性相关的for循环与LOGN复杂外环 [英] complexity of two dependent for loops with outer loop of logn complexity

问题描述

问题

计算算法的复杂度：

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

之前，我做了关于这一主题：

第一循环中运行LOGN次。 第二循环运行妮次，我从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 + 1）不能在其上的应用。我如何进一步开展与此解决方案，或者如果它是错的，那么什么是正确的方法。

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 + 1）加，由此产生的复杂性是 -n /（2 ^ N）= O（2 ^ n）的。

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

推荐答案

您是在正确的轨道上。至于你提到的内循环将执行日志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循环与LOGN复杂外环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！