algorithm - 寻找最大子数组和算法的 big-omega

Question

我有一个算法，我正在尝试找出解决最大子数组和问题的该算法的最佳情况(渐近表示法):

-- Pseudocode --

// Input: An n-element array A of numbers, indexed from 1 to n.
// Output: The maximum subarray sum of Array A.

Algorithm MaxSubSlow(A):
    m = 0.
    for j = 1 to n do:
        for k = j to n do:
            s = 0
            for i = j to k do:
                s = s + A[i]
            if s > m then:
                m = s
    return m

查看算法，使用渐近符号数学很容易确定最坏情况(每个循环运行，在最坏情况下，所有 n 次)所以最坏情况的复杂度等级为 O(N^3 ).

然而，我的教科书指出该算法也运行在 Big-Omega(N^3) 时间内；也就是说，下限等于其上限。不过，它没有解释原因。

您将如何正式计算并证明这一点？您是否必须证明对于该算法，存在数字子集 (i, j, k) 使得算法中的每个循环至少运行 n 次？如果是这样，你是怎么做到的？

Answer 1

直观上，即使您更改输入以保持相同的大小 n，它也会执行相同数量的操作:操作的数量仅取决于输入大小，而不取决于具体的输入。所以最好和最坏的情况是一样的。

在这种情况下，o() 的计算与 O() 完全相同