算法复杂度为这个函数

def mystery(L): 

sum1 = 0 
sum2 = 0 
bound = 1 
while bound <= len(L): 
    i = 0 
    while i < bound: 
     j = 0 
     while j < len(L): 
      if L[j] > L[i]: 
       sum1 = sum1 + L[j] 
      j = j + 2 
     j = 1 
     while j < len(L): 
      sum2 = sum2 + L[j] 
      j = j*2 
     i = i + 1 

    bound = bound * 2 
return sum1 + sum2

我很难找到这个函数的复杂性。我到了我的循环，不知道该怎么做。算法复杂度为这个函数

来源

2016-03-27 user6121972

要理清中间级别循环运行的次数有点棘手。外循环在每次传递中增加bound两倍（最多len(L)），这意味着i循环将每次传球O(bound)次，对于O(log(N))传球（其中N是len(L)）。棘手的部分是如何合计bound值，因为它们在每次传递中都会发生变化。

我认为找出总和最简单的方法是从循环退出前最大的bound开始。首先，我们假设N（又名len(L)）是2的幂。那么最后的bound的值将完全等于N。下一个较小的（在最后一次迭代中使用的）将是N/2，接下来的将是N/4。它们的和将是：

N + N/2 + N/4 + N/8 + ... + 1

如果我们从每学期分解出N，我们会得到：

N*(1 + 1/2 + 1/4 + 1/8 + ... + 1/N)

你应该认识到在括号中的总和，这是一个简单的几何级数（总和1/2）的权力，这在数学和分析中很常见。如果总和持续下去，它会加起来到2。由于我们提前退出，它将少于两个相当于上一期的金额（1/N）。当我们再次乘N来看，我们得到了整个事情的正在运行2*N - 1倍，因此该循环是O(N)

同样的BIG-O密集型工作时N是不完全的2的幂，因为价值观我们在上面的分析中加起来将分别作为我们将在循环中看到的实际值bound之一的上限。

因此，i循环运行O(N)次。

来源

2016-03-28 03:50:35 Blckknght

算法复杂度为这个函数

回答

相关问题