在我的函数修复中，2 个嵌套 while 循环的时间复杂度如何为 o(N)？

Question

输入 = [10, 9, 7, 18, 13, 19, 4, 20, 21, 14]输出：10 9 18 7 20 19 4 13 14 21def fixing(arr):    oddIdx = 1    evenIdx = 0    while True:        while evenIdx < len(arr) and arr[evenIdx] %2 ==0:            evenIdx +=2        while oddIdx < len(arr) and arr[oddIdx] % 2!=0:            oddIdx+=2        if evenIdx < len(arr) and oddIdx < len(arr):            arr[evenIdx], arr[oddIdx] = arr[oddIdx], arr[evenIdx]        else:            break    return arr是因为我们没有忽略外循环吗？如果是，为什么，如果不是，为什么不呢？谢谢你！

Answer 1

让我们分解一下。

的条件while True取决于evenIdx < len(arr) and oddIdx < len(arr)。

所以外循环不会迭代超过 O(N) where N=len(arr)。

但是内循环呢？

让我们考虑这里的选项：

1. 我们只有 1 次外部循环迭代，其中内部函数前进evenIdx并oddIdx到达中断点。所以整体 O(N)。

2. 外层循环迭代 K 次。但是evenIdx，oddIdx 不要重置。在第 1 次迭代中，evenIdx/oddIdx到达 0 到 N 之间的某个位置，第 2 次迭代它们仍然继续前进，第 3 次迭代相同，直到第 K 次迭代。最终evenIdx/oddIdx前进了 O(N) 次。所以又是O(N)。

可以进行更严格的分析，但仍然是 O(N)。

Answer 2

这是因为您没有通过外循环每次都重置evenIdx或oddIdx返回。0每次重复外循环时，内循环都会从上一次停止的地方开始。

因此，您不会对列表执行多次迭代——只要两个内部循环都到达末尾，您就会跳出外部循环。并且每个内部循环只访问偶数或奇数元素一次。