滑动窗口算法内循环时间复杂度

Question

我正在看LeetCode问题1838。最常见元素的频率:

元素的频率是它在数组中出现的次数。

您将获得一个整数数组

nums

和一个整数

k

。在一项操作中，您可以选择索引

nums

并将该索引处的元素增加

1

。

执行最多k操作后，返回元素的

最大可能频率

。

我有这种滑动窗口方法可以解决这个问题：

def maxFrequency(self, nums: List[int], k: int) -> int:
    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(𝑛)。

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