嵌套循環的複雜性（復發關係）

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

嵌套循環的複雜性（復發關係）

回答

相關問題