为何这段数组处理函数的时间复杂度是O(n²)？求解析

问题描述 #

给定如下伪代码实现的数组处理函数，已识别出一处O(n)的复杂度，但无法理解为何整体时间复杂度为O(n²)，请求解答：

function F(A :Array){
    i=1
    j=1
    m=0
    c=0
    while i<=Size(A) do
        if A[i]=A[j] then
            c=c+1
        end if
        j=j+1
        if j>Size(A) then
            if c>m then
                m=c
            end if
            c=0
            i=i+1
            j=i
        end if
    end while
return m

复杂度分析 #

要理解整体时间复杂度，核心是统计循环体的总执行次数：

• 设数组长度为n（即Size(A)=n），变量i的取值范围是1到n。
• 对于每一个i，变量j都会从i开始，一直遍历到数组末尾（直到j>Size(A)触发i递增）。

总执行次数为：

n + (n-1) + (n-2) + ... + 1 = n*(n+1)/2

根据大O表示法的规则，忽略低次项和常数系数，该表达式的最高次项为n²，因此整体时间复杂度为O(n²)。

直观示例验证 #

假设n=4：

• i=1时，j从1到4，执行4次循环体
• i=2时，j从2到4，执行3次循环体
• i=3时，j从3到4，执行2次循环体
• i=4时，j从4到4，执行1次循环体
  总执行次数：4+3+2+1=10次，对应公式计算结果4*5/2=10，完全匹配。

你可能误以为的O(n)是单次j遍历的复杂度，但实际上i会触发n次这样的遍历，每次遍历的长度递减，最终累计成平方级的总操作量。

内容的提问来源于stack exchange，提问作者Felix Hajj