algorithm - 嵌套循环的复杂性(递推关系)

Question

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)。但是，我需要内循环的确切执行次数，以便通过递归关系证明这一点。

Answer 1

不就是 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。