内循环的时间复杂度

Question

我有这段代码可以解决 LeetCode 问题#1838：

    nums.sort()
    res,curSum = 0,0
    l = 0
    for r in range(len(nums)):
        total = nums[r] * (r-l+1) # the goal
        curSum += nums[r] # what we currently have

        # check if we have enough operations to reach our goal
        while total - curSum > k:
            # remove L until we have valid subsequence
            curSum -= nums[l]
            l += 1
            total = nums[r] * (r-l+1)
     
        res = max(res, r-l+1)
    
    return res

网上和讨论板上都说这种方法的运行时间为 O(nlogn)，因为它受到 nums 数组排序的瓶颈，但我不明白计算过程。

我假设 for 循环的运行时间为 O(n)，内部 while 循环的最坏情况运行时间也为 O(n)。这样一来，程序的时间复杂度岂不是 O(nlogn) + [O(n) * O(n)] = O(nlogn) + O(n^2) = O(n^2) 吗？我的问题是为什么循环的组合运行时间是 O(n) 而不是 O(n^2)。如果有人能帮助向我解释这个想法，我将非常感激！

Answer 1

为什么循环的组合运行时间是 O(n) 而不是 O(n^2)。

l

的值是理解这一点的关键。它表示内部循环在算法完整执行过程中将进行的迭代次数。 由于

l

不会超过输入的大小，因此内循环体的执行总数不会超过𝑛。

这就是为什么它不会将总复杂度从 O(𝑛) 增加到 O(𝑛²)。仍然是 O(𝑛)。

因此，排序操作确实是复杂性方面的瓶颈。