嵌套循环的复杂性（复发关系）

Algorithm-1 (A:array[p..q] of integer) 
    sum, max: integer 
    sum = max = 0 
    for i = p to q 
     sum = 0 
     for j = i to q 
      sum = sum + A[j] 
      if sum > max then 
       max = sum 
    return max

嵌套循环执行多少次？嵌套循环的复杂性（复发关系）

我知道第一个for循环的复杂度为O(n)，整个算法的总复杂度为O(n^2)。但是，我需要内循环的确切执行次数，以便通过递归关系证明这一点。

来源

2012-11-01 Taylor Jones

岂不只是Sum(i = 1 -> n, i)，相当于n(n+1)/2？

在你的情况，n = q-p+1，所以你得到(q-p+1)(q-p+2)/2。

扩大了这一点 - 如果我这样做的权利 - 你得到(q^2-qp+2q-pq+p^2-2p+q-p+2)/2 = (q^2+p^2-2qp+3q-3p+2)/2。

来源

2012-11-01 02:21:36

可能不是你要找的答案。事实上，你知道内部循环有O（n）并且整个程序具有O（n^2）复杂性。只需投入计数器并将其增加到内部循环中即可。这应该给你确切的执行次数。

来源

2012-11-01 02:17:14

如果你想要一个确切的数字，内环调用(n + n-1+ ...1) = n(n+1)/2 ~= O(n^2)

这里n = q-p

来源

2012-11-01 02:17:47

内环运行Q-i + 1周的时间和执行的总数是

\总和{I = P}^{Q}（Q-I + 1）= \和{k = 1时（k）= n *（n + 1）/ 2

其中n = q-p + 1。

来源

2012-11-01 02:53:24 nmoses

嵌套循环的复杂性（复发关系）

回答

相关问题