1

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)，是因为嵌套循环吗？谢谢

4

2 回答 2

1

额外的空间复杂度为 O(1)。那是因为交换不依赖于输入长度吗？

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

时间复杂度，给定为 O(N^2)，是因为嵌套循环吗？

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

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

于 2018-08-02T19:26:09.140 回答
1

额外的空间复杂度为 O(1)。那是因为交换不依赖于输入长度吗？

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

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

  • pivot只是对列表成员之一的引用，它是常量大小。
  • arange是常数大小。
  • a 上的迭代器range是固定大小的。
  • 范围迭代器返回的i和j整数值是常量大小。1
  • …</li>

由于没有什么比恒定大小大，所以总大小是恒定的。

时间复杂度，给定为 O(N^2)，是因为嵌套循环吗？

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

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

所以，第一遍确实：

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

所以，如果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，以及对象的stop属性range，可能还有一些其他的东西都是log N. 但是，除非您处理的是大整数运算，例如在乘以大素数的加密算法中，否则人们通常会忽略这一点并侥幸逃脱。

于 2018-08-02T19:33:28.017 回答