8

可能重复：
Big O 的简单英文解释

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

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

编辑：我在这里发布之前搜索了教程。不幸的是，所有的教程都集中在运行时复杂度上，几乎没有写超过几行关于空间复杂度的内容。

4

1 回答 1

10

根据您想要跳入的位置，这可能是一个很好的脚趾斗。wiki页面的质量也很高，而且更深入一些。 这是一本很好的高年级本科生或研究生入门教材，将涉及线性加速定理，这是计算机科学家在讨论算法运行时完全使用大 O 表示法的一个重要原因。简而言之，它说你总是可以通过在硬件上投入成倍的金钱来获得速度提升的线性因素。

Big-O 表示法的优点在于它允许我们丢弃成本公式末端的“零钱”。这是由一个隐含的假设证明的，即我们只关心输入的大小变为无穷大的极限情况，而我们成本的最大项支配其他项。

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

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

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

例如，如果冒泡排序等算法将项目数组作为输入，则典型的度量是数组的长度。假设我们希望计算它在最坏情况下进行的交换次数。这是它的伪代码，取自维基百科：

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' 的聪明之处在于它的定义为容纳我们的动机提供了严格的框架。事实证明，该框架说我们放弃了主要的常数因素。

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

一旦你证明了一个公式，在 big-O 中“减少”它是一项不同的技能，本质上需要知道一点微积分（极限）。最终，你将能够通过确定它们的术语来剪除证明中烦人的分支介绍将由其他一些已知的主导。

于 2011-09-05T09:56:41.220 回答