O(1) space 奇偶复杂度

Question

我正在对数组的条目重新排序，以便偶数（可被 2 整除）首先出现。代码片段如下：

def even_odd(A):
    next_even , next_odd = 0, len(A) - 1
    while next_even < next_odd:
        if A[next_even] % 2 == 0:
           next_even += 1
        else:
           A[next_even], A[next_odd] = A[next_odd], A[next_even]
           next_odd -= 1

时间复杂度为 O(N)，我猜这是因为我要遍历整个数组？但是 space 复杂度如何 O(1)？

Answer 1

我猜这里的意思是重新排序需要的"additional"内存为o(1)，排除了原数组。

Answer 2

您使用固定数量的 space 重新排序列表。根据定义，这就是 O(1)。事实上，你处理的长度 A 并不影响你的函数的 space 用法：A 已经被问题分配了定义。您所添加的只是两个整数，next_even 和 next_odd：它们是您的 O(1).

根据 OP 评论更新

A 的大小不会 "count against" 您的 space 复杂性，因为您的算法使用调用程序已经提供的 space。您还没有添加任何内容。

对不起；我没有意识到你有一个关于时间复杂度的悬而未决的问题。是的，您的猜测是正确的：您经历了 while 循环 N-1 次 (N = len(A) )；每次迭代所花费的时间不会超过固定的时间量。因此，时间复杂度受限于 N.

O(1) space 奇偶复杂度

O(1) space complexity for odd-even

python

arrays

time-complexity

space-complexity