算法空间复杂性教程

Question

可能重复： “大O”的简明英语解释

我一直在努力计算我编写的算法的大O时间和空间复杂度。

谁能指出一个好的资源来研究更多关于算法的空间复杂性。

编辑:我在这里发布之前搜索过教程的。不幸的是，所有的教程都集中在运行时复杂性上，很少有几行是关于空间复杂性的。

Answer 1

根据你想跳槽的地方，这可能是个不错的跳伞者。维基页面也是高质量的，而且更深入一些。这是一个很好的高级本科或入门研究生文本，并将进入线性加速比定理，这是计算机科学家在讨论算法运行时使用大O表示法的一个很大原因。简而言之，它说，你总是可以得到一个线性因素的速度提高，投入指数金额的硬件。

大O符号的优雅之处在于它允许我们抛弃我们的成本公式的末端的“松散变化”。这是合理的，隐含的假设，我们只关心极限情况下，我们的投入到无穷大，我们最大的条件，我们的成本占主导地位的其他。

执行复杂性分析要求您首先为您的输入选择一个度量，然后决定您希望度量其消耗的资源，然后计算算法在给定大小的输入上运行时所占的量。按照惯例，输入大小被命名为N。典型的资源是执行的“步骤”数量或存储在所有容器中的项，但这些只是(流行的)例子。相比之下，基于比较的排序算法通常只关注掉期的数量.

通常情况下，输入的大小并不是算法运行所需的时间或所需空间的唯一决定因素。例如，插入排序的运行时间在以已排序和反向排序顺序表示的相同长度的输入之间有很大的不同。这就是为什么我们谈论最坏的情况和平均情况的复杂性(或最好的情况，等等)。通过询问“可能发生的最糟糕的事情是什么？”，我们可以决定如何通过源并计算使用量。

一般情况的复杂性是很棘手的，因为它们需要了解可能的输入的分布情况。最坏情况的复杂性与输入分布无关，并为我们提供了硬上界，这在实践中往往是我们所需要的。

例如，如果像气泡分类这样的算法以一个项数组作为输入，一个典型的度量就是数组的长度。假设我们希望在最坏的情况下计算掉期的数量。下面是它的伪代码，摘自Wikipedia：

procedure bubbleSort( A : list of sortable items )
  repeat
    swapped = false
    for i = 1 to length(A) - 1 inclusive do:
      if A[i-1] > A[i] then
        swap( A[i-1], A[i] )
        swapped = true
      end if
    end for
  until not swapped
end procedure

注意，它本质上是两个for循环，一个内部嵌套在另一个循环中。内部循环从1到length(A) - 1进行计数，并在数组的最大元素位于最前面时进行最大N - 1交换。外部循环重复此过程，只要最后一遍发生任何交换。假设前面是最坏的情况，之前最大的未排序元素将位于列表的末尾，有效地缩小了我们可以移动下一个最大的未排序元素的距离。因此，每一次连续的传递都会减少一次交换，最后我们将

N + (N-1) + (N-2) + ... + 2 + 1 = N * (N + 1) / 2 = 1/2 * N^2 + N/2

在大O表示法中，这变成

O(1/2 * N^2 + N/2) = O(1/2 * N^2) = O(N^2)

在这里，我们删除了线性(N/2)项，因为它将被二次项( N -> inf )所主导。然后，我们删除1/2主导常数因子，因为它本质上是一个硬件细节。注意，这是人类的动机：“大O”的聪明之处在于它的定义为我们的动机提供了一个严格的框架。原来这个框架说我们放弃了主导不变的因素。

精确地证明复杂性本身就是一项技能，仅仅了解定义并不能对你有多大帮助。归纳证明通常适用于这样的情况:在循环的每一次传递周围都要建立前置条件和后条件.注意，在我的非正式论证中，我在对当前的迭代进行推理时考虑到了前面的迭代:这是归纳思维。“离散数学”、“归纳证明”、“组合数学”和“计数”都是很好的关键词。(是的，“数”本身就是数学的一个分支，而且很难。)

一旦你证明了一个公式，在大O中“减少”它是一种不同的技能，本质上需要知道一些微积分(极限)。最终，你将能够在你的证明中剪除恼人的分支，方法是确定它们所引入的术语将被其他已知的术语所支配。