算法空间复杂度教程
可能重复：
Big O的纯英文解释
我一直在努力计算我写的算法的大O时间和空间复杂度。
任何人都可以指出一个很好的资源来研究算法的空间复杂性。
编辑：我在这里发布之前搜索了教程。 不幸的是，所有的教程都着眼于运行时间的复杂性，并且几乎不会在空间复杂度上写出更多的内容。
取决于你想跳到哪里，这可能是一个很好的脚趾。 维基页面也是高质量的，并且深入一点。 这是一个很好的高年级本科或研究生入门文章，并将进入线性加速定理，这是计算机科学家在讨论算法运行时时使用大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
在大O符号这成为
O(1/2 * N^2 + N/2) = O(1/2 * N^2) = O(N^2)
在这里，我们放弃线性（ N/2 ）项，因为它将被二次方控制为N -> inf 。 然后我们放弃1/2主导恒定因子，因为它本质上是一个硬件细节。 注意这是一个人的动机：大O的聪明是它的定义提供了一个严格的框架来保存我们的动机。 结果表明，我们放弃了领先的常数因素。
制定一个严格的复杂性证明本身就是一项技巧，仅仅知道定义对你来说无助。 通过归纳证明通常是适用的，其中在循环的每次通过周围都建立了前置条件和后置条件。 请注意，在我的非正式论证中，我推论了当前推理的一个迭代：这是归纳思考。 “离散数学”，“归纳证明”，“组合”和“计数”都是很好的关键词。 （是的，“计数”本身就是数学的一个分支，而且很难。）
一旦你已经证明了一个公式，在大O中“减少”它是一种不同的技能，并且本质上需要知道一点微积分（限制）。最终，你将能够通过确定他们的条件来删除令人讨厌的分支介绍将由一些其他已知的人主导。
链接地址: http://www.djcxy.com/p/6753.html