Remove Shift算法跨方法嵌套for循环的大O时间复杂度是多少？

Method(main)
    for i=1 to n 
        if isDuplicate (i)
            remove (i)
        endif
    endfor
return n

Method: isDuplicate (i)
    for j=1 to n
        if A[j] = A[i]
            return true
        endif
    endfor
    return false

Method: remove (i)
// Removes and performs a left-shift.
    for j=n-1 to i
        A[j] = A[j+1]
    endfor
    n = n -1

结论 #

该算法的最坏时间复杂度为O(n²)，既不是O(n)，也不是你猜测的O(n³)。

详细分析 #

• 首先明确最坏测试场景：数组内所有元素完全相同，此时每次外层循环都会触发isDuplicate返回true，进而执行remove操作。
• 误区纠正：你可能误以为isDuplicate和remove两个O(n)操作在外层循环中会形成三层嵌套，实际上二者是同一层级的先后执行关系，只有嵌套循环才会做复杂度相乘，同层操作是复杂度相加。
• 各部分开销计算：
  1. 外层循环的迭代次数最多为初始n次，属于O(n)量级
  2. 每次迭代必然执行isDuplicate，该方法最坏情况下遍历当前所有数组元素，单次开销为O(n)，总开销为O(n)*O(n) = O(n²)
  3. 最坏场景下每次迭代都会执行remove，左移操作单次最坏开销为O(n)，总开销为O(n)*O(n) = O(n²)
• 合并总开销：两部分O(n²)的操作相加，最终时间复杂度仍为O(n²)。

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