algorithm - 算法空间复杂度教程

Question

这个问题在这里已经有了答案:




10年前关闭。

Possible Duplicate:
Plain English explanation of Big O

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

任何人都可以指出一个很好的资源来研究更多关于算法的空间复杂性。

编辑:我在这里发帖之前搜索过教程。不幸的是，所有的教程都专注于运行时复杂度，几乎没有写过几行关于空间复杂度的内容。

Answer 1

取决于您想跳入的位置，this可能是一个很好的脚趾头。 wiki页面质量也很高，而且更深入一些。 This是一本不错的高年级本科或研究生入门教材，会进入linear speedup theorem ，这是计算机科学家在讨论算法运行时完全使用大 O 符号的一个重要原因。简而言之，它说你总是可以通过在硬件上投入大量资金来获得速度提升的线性因素。

Big-O 符号的优点在于它允许我们丢弃成本公式末端的“松散变化”。这是由隐含假设证明的，即我们只关心输入的大小达到无穷大的极限情况，并且我们的成本的最大项支配其他项。

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

输入的大小通常不是算法运行时间或需要多少空间的唯一决定因素。例如，插入排序的运行时间在以已排序和反向排序顺序呈现的等长输入之间存在显着差异。这就是我们谈论最坏情况与平均情况复杂度(或最佳情况等)的原因。通过询问例如“可能发生的最糟糕的事情是什么？”，我们可以决定如何遍历源并计算用法。

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

例如，如果算法如 Bubble Sort将一组项目作为输入，典型的度量是数组的长度。假设我们希望计算它在最坏情况下进行的掉期次数。这是它的伪代码，取自维基百科:

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

在 Big-O 符号中，这变成

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

在这里，我们放弃线性 ( N/2 ) 项，因为它将以二次项为主，如 N -> inf .然后我们放下 1/2主要常数因子，因为它本质上是一个硬件细节。请注意，这是人类的动机:big-O' 的巧妙之处在于它的定义为容纳我们的动机提供了一个严格的框架。事实证明，该框架说我们放弃了主要的常数因素。

制作复杂性的严格证明本身就是一项技能，仅了解定义对您没有多大帮助。 Proof by induction通常适用，其中围绕循环的每次传递建立前置条件和后置条件。请注意，在我的非正式论证中，我在推理当前迭代时考虑了前一个迭代:这是归纳思维。 “离散数学”、“归纳证明”、“组合数学”和“计数”都是很好的关键词。 (是的，“计数”本身就是数学的一个分支，很难。)

一旦你证明了一个公式，在大 O 中“减少”它是一项不同的技能，基本上需要知道一点微积分(限制)。最终，你将能够通过建立它们的术语来修剪证明中烦人的分支介绍将被其他一些已知的主导。