了解两个嵌套 while 循环中的时间复杂度

Question

我遇到了这个代码。它只扫描数组元素一次。但我对有两个嵌套的while循环将复杂性增加到O（n^2）感到困惑。代码如下：

def summaryRanges(nums):
    x, size = 0, len(nums)
    ans = []
    while x < size:
        c, r = x, str(nums[x])
        while x + 1 < size and nums[x + 1] - nums[x] == 1:
            x += 1
        if x > c:
            r += "->" + str(nums[x])
        ans.append(r)
        x += 1
    return ans

我正在学习算法，所以如果我哪里出了问题，请纠正我。非常感谢。

Answer 1

你的问题不是100%清楚，但如果你的意思是为什么这不是O(N^2)而有嵌套循环，那么:

虽然有嵌套循环，但它们使用相同的变量在相同的空间上运行以推进迭代。由于内部循环不会回溯，并且每当它向前移动时，它也会将外部循环向前推（在完全相同的距离上），如果N增长M（如果N1=N0 M），迭代不会增长到M。O（N^2）意味着随着N的增长，迭代呈指数增长。