Space-荷兰国旗变化的时间复杂度

Question

DNF的变体如下：

def dutch_flag_partition(pivot_index , A):
    pivot = A[pivot_index]
    # First pass: group elements smaller than pivot.
    for i in range(len(A)):
      # Look for a smaller element.
        for j in range(i + 1, len(A)):
           if A[j] < pivot:
             A[i], A[j] = A[j], A[i]
             break

# Second pass: group elements larger than pivot.

for i in reversed(range(len(A))):
    if A[i] < pivot:
      break
    # Look for a larger element. Stop when we reach an element less than
    # pivot , since first pass has moved them to the start of A.
    for j in reversed(range(i)):
       if A[j] > pivot:
         A[i], A[j] = A[j], A[i]
         break

额外的 space 复杂度为 O(1)。那是因为交换不依赖于输入长度吗？时间复杂度为 O(N^2)，是嵌套循环造成的吗？谢谢

Answer 1

The additional space complexity is given as O(1). Is that because the swapping doesn't depend on the input length?

当您 "just" 交换时，没有创建或生成新数据，您只是在重新分配已有的值，因此 space 复杂度是恒定的。

And time complexity, given as O(N^2), is it so due to the nested loops?

没错。这是二阶多项式时间复杂度，因为您嵌套了两个 for 循环。

你有一个 break，所以在更有利的情况下，你的时间复杂度将低于 N^2。但是，由于 big-O 是最坏的情况，所以可以说它是 2 度。

Answer 2

The additional space complexity is given as O(1). Is that because the swapping doesn't depend on the input length?

没有。事实上，交换根本不需要额外的 space。

更重要的是，你不能只寻找一件事然后说不管这件事需要多少，这就是复杂性。你得把所有的东西都看一遍，最大的一个决定了复杂度。因此，查看您正在创建的所有内容：

pivot 只是对列表成员之一的引用，它是恒定大小。
a range 大小不变。
range 上的迭代器大小不变。
范围迭代器返回的 i 和 j 整数值是恒定大小。¹
…

因为没有什么比常量大，所以总大小是常量。

And time complexity, given as O(N^2), is it so due to the nested loops?

嗯，是的，但你必须比这更详细一点。两个嵌套循环并不一定意味着二次循环。在嵌套循环内做线性工作的两个嵌套循环将是立方体。两个嵌套循环的组合使得内循环的大小与外循环成反比，它们是线性的。等等。

再说一次，你必须把所有的东西都加起来，而不是只挑一件事然后猜测。

所以，第一遍是：

普通列表索引和赋值，常量。
输入长度的循环。
- …在输入长度上有一个循环
- ... 有一些列表索引、比较和赋值，都是常量
- …在某些情况下也会提前中断…我们可以回来。

所以，如果 break 根本没有帮助，那就是 O(1 + N * N * 1)，也就是 O(N * N)。

第二遍同样是O(N * (1 + N * 1))，又是O(N * N)。

如果你加上 O(N * N + N * N)，你会得到 O(N * N)。

此外，即使 break 使第一遍对数线性或类似的东西，O(N * log N + N * N) 仍然是 O(N * N)，所以没关系。

所以时间是二次方的。

_{1.从技术上讲，这并不完全正确。整数是可变大小的，它们占用的内存是它们大小的对数。所以，i 和 j，以及 range 对象的 stop 属性，可能还有一些其他东西都是 log N。但是，除非你处理的是大整数运算，比如乘以巨大质因数的加密算法，否则人们通常会忽略这一点，然后侥幸逃脱。}

Space-荷兰国旗变化的时间复杂度

Space-Time complexity in variation of Dutch National Flag

python

time-complexity

space-complexity

dutch-national-flag-problem