关于矩形覆盖贪心算法的时间复杂度分析问询

我有一项贪心算法作业，写了解决“矩形覆盖”问题的MinGreedyCutReg代码，但拿不准它的时间复杂度。我觉得是O(n*m)，朋友认为是O(n²)，想明确嵌套循环的时间复杂度及原因。

代码如下：

MinGreedyCutReg(R[])
    cut[] = null
    while R != null
        endIndex = 0
        for i = 0 to R.length-1
            if(endIndex < R[i].r)
                endIndex = R[i].r
        maxCount = 0
        maxIndex = 0
        for i = 0 to endIndex
            updateMax = 0
            for j = 0 to R.length - 1
                if(R[j].l <= i and R[j].r >= i)
                    updateMax++
            if(updateMax > maxCount):
                maxCount = updateMax
                maxIndex = i
        cut.add(maxIndex)
        for i = 0 to R.length - 1
            if(R[i].l <= maxIndex and R[i].r >= maxIndex)
                R.remove(i)
    return cut

时间复杂度拆解分析 #

咱们一步步扒代码里的循环开销：

1. 外层while循环：每次循环至少会移除一个矩形（选的maxIndex必然覆盖至少一个矩形），所以最多执行n次（n是初始矩形总数）。
2. 第一个for循环（求endIndex）：遍历当前剩余的k个矩形（k从n递减到1），单次开销O(k)，累计下来是n + (n-1) + ... + 1 = O(n²)。
3. 中间嵌套循环（找maxIndex）：
   • 外层遍历从0到endIndex，假设所有矩形的最大右边界是m，这层开销是O(m)。
   • 内层遍历当前剩余的k个矩形，单次开销O(k)。
   • 这部分单次while循环的开销是O(mk)，累计下来就是m(n + (n-1) + ... +1) = O(m*n²)。
4. 最后一个移除矩形的循环：遍历当前k个矩形，移除操作如果是数组实现的话，每次移除要移动后续元素，总开销也是O(k)，累计下来同样是O(n²)。

关于你和朋友的分歧 #

• 你认为的O(n*m)，应该是只算了单次while循环里中间嵌套的开销，但忽略了while循环会执行n次，最坏情况下总复杂度要再乘n。
• 朋友说的O(n²)，是假设m是固定常数（比如所有矩形的右边界都不超过某个固定值），这时候m可以被忽略，总复杂度简化为O(n²)。

但最坏情况下的时间复杂度是O(m*n²)——当m和n同阶（比如每个矩形的右边界随n增大而线性增长）时，复杂度就是O(n³)。

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