python - 荷兰国旗变化的时空复杂度

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

额外的空间复杂度为 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?

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

更重要的是，你不能只寻找一件事，然后说无论这件事需要付出多少努力，这就是复杂性。你必须检查所有事物，而最大决定了复杂性。因此，请检查您正在创建的所有内容:

• pivot 只是对列表成员之一的引用，其大小恒定。
• 范围是恒定大小。
• 范围上的迭代器的大小是恒定的。
• 范围迭代器返回的 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 属性，可能还有其他一些东西都是记录N。但是，除非你处理的是巨大的整型算术，比如在加密算法中乘以巨大的质因数，否则人们通常会忽略这一点，并侥幸逃脱。