算法空间复杂度教程

Question

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

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

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

编辑:我在发布之前搜索过教程.遗憾的是,所有教程都侧重于运行时复杂性,并且几乎没有写太多关于空间复杂性的内容.

Answer 1

根据您想要跳入的位置,这可能是一个好的脚趾铲.在维基页面也高品质,并进入深度多一点. 这是一个很好的高年级本科或研究生文本,并将进入线性加速定理,这是计算机科学家在讨论算法运行时时使用big-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循环,一个内部嵌套在另一个循环中.内部循环从1to开始计数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'的聪明之处在于它的定义为我们的动机提供了一个严格的框架.事实证明,该框架表明我们放弃了领先的常数因素.

制作严格的复杂性证明本身就是一项技能,仅仅了解定义对您来说无济于事. 通过归纳证明通常是适用的,其中一个循环的每次通过建立前置条件和后置条件.请注意,在我的非正式论证中,我在推理当前的迭代时会考虑前一次迭代:这是归纳思维."离散数学","归纳证明","组合学"和"计数"都是很好的关键词.(是的,"计数"本身就是数学的一个分支,而且很难.)

一旦你已经证明了的公式,"减少",它在大O是一个不同的技能,而且基本上需要知道一点微积分(限).最终,你将能够通过建立以精简掉在你的证明恼人的分支机构的条件,他们介绍将由其他已知的一个主导.