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

Question

输入 = [10, 9, 7, 18, 13, 19, 4, 20, 21, 14]

输出：10 9 18 7 20 19 4 13 14 21

def 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&nbsp;N=len(arr)。但是内循环呢？让我们考虑这里的选项：我们只有 1 次外部循环迭代，其中内部函数前进evenIdx并oddIdx到达中断点。所以整体 O(N)。外层循环迭代 K 次。但是evenIdx，oddIdx&nbsp;不要重置。在第 1 次迭代中，evenIdx/oddIdx到达 0 到 N 之间的某个位置，第 2 次迭代它们仍然继续前进，第 3 次迭代相同，直到第 K 次迭代。最终evenIdx/oddIdx前进了 O(N) 次。所以又是O(N)。可以进行更严格的分析，但仍然是 O(N)。

Answer 2

这是因为您没有通过外循环每次都重置evenIdx或oddIdx返回。0每次重复外循环时，内循环都会从上一次停止的地方开始。因此，您不会对列表执行多次迭代——只要两个内部循环都到达末尾，您就会跳出外部循环。并且每个内部循环只访问偶数或奇数元素一次。