可能的重复项：
大O的简明英文解释
我一直在努力计算我编写的算法的 Big-O 时间和空间复杂性。
任何人都可以指出一个很好的资源来研究更多关于算法的空间复杂性。
编辑：在这里发布之前，我已经搜索了教程。不幸的是，所有教程都侧重于运行时复杂性，几乎没有写超过几行空间复杂性。
根据你想跳进去的地方，这可能是一个很好的脚趾。 维基页面的质量也很高，并且更深入一些。 这是一个很好的高年级本科或入门研究生文本，并将进入线性加速定理，这是计算机科学家在讨论算法运行时使用大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中"减少"它是一个不同的技能，本质上需要知道一点微积分(极限(。 最终，您将能够通过确定它们引入的术语将由其他已知术语主导来修剪证明中烦人的分支。