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

可能不是您要找的答案。事实上，你猜对了，内循环的复杂度为 O(n)，整个程序的复杂度为 O(n^2)。只需放入一个计数器并在您的内部循环中递增它。这应该会给你确切的执行次数。

Answer 2

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

这里n = q-p

Answer 3

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

Answer 4

内循环运行q-i+1次，总执行次数为

\sum{ i=p }^{ q } (q-i+1) = \sum{ k=1 }^{ q-p+1 } (k) = n * (n+1) /2

其中 n = q-p+1。