算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别。

衡量算法的优劣，主要是从时间和空间两个维度考量。

算法的时间复杂度和空间复杂度，合称为算法复杂度。

大O表示法

大O表示法：算法的时间复杂度通常用大O符号表述，定义为 **T[n] = O(f(n)) **。称函数T(n)以f(n)为界或者称T(n)受限于f(n)。

如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)。T(n)称为这一算法的“时间复杂度”。

大O符号是一种算法「复杂度」的「相对」「表示」方式。

时间复杂度

时间频度

一个算法执行所消耗的时间，理论上是不容易算出来的，必须上机运行进行测试才知道。实际情况下，我们不可能把算法都上机运行一下。我们只需要知道哪个算法的用的时间多，哪个用的时间少就可以了。并且一个算法的的花费时间与语句运行次数成正比，哪个算法执行语句多那么所用时间就多。一个算法中的语句执行次数称为语句频度或时间频度，记为 T(n)。

时间复杂度

时间频度 T(n) 中，n 称为问题的规模，当 n 不断变化时，时间频度 T(n) 也会跟着变化。但有时我们想知道它的变化成怎样的趋势时或者有什么样的规律。为此，引入了时间复杂度的概念。一般情况下，算法中基本操作的重复执行的次数是问题规模n的某个函数，用 T(n) 表示。若有某个辅助函数 f(n),使得当 n 趋近于无穷大时，T(n)/f(n) 的极限值为不等于0的常数，则称为 f(n) 是 T(n) 的同数量级函数，记做T(n)=O(f(n))，称 O(f(n)) 为算法的渐近时间复杂度，简称时间复杂度。

最坏时间复杂度

运行时间最长的算法的时间复杂度，也就是算法的上界，一般没有特指我们讨论的时间复杂度就是指最坏时间复杂度，不管这个问题有多少种思路解决，它的算法运行时间不会超过这个时间上限。

平均时间复杂度

所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。

常见的复杂度量级

O(1)

• 常阶数 O(1)，常数时间运行。
• 比如操作对象为一个链表，对其有一个算法，O(1) 时间指的是，无论链表大或者小，所耗费的时间都是一样的

O(n)

• 线性阶 O(n)，算法的运行时间与输入规模成正比
• 若输入规模为 T，花费时间为 N。则输入规模2T时花费时间为2N
• 比如操作对象为一个集合，对其进行遍历操作，集合长度越大，所耗费的时间会越长

O(n²)

• 平方阶 O(n²)
• 当存在双重循环的时候，即把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²)

O(logn)

• 对数阶 O(logn)
• 在二分查找法的代码中，通过 while 循环，成 2 倍数的缩减搜索范围，也就是说需要经过 log2^n 次即可跳出循环

O(nlogn)

• 线性对数阶 O(nlogn)
• 将时间复杂度为 O(logn) 的代码循环N遍的话，那么它的时间复杂度就是 n * O(logn)，也就是了O(nlogn)

空间复杂度

空间复杂度可以理解为除了原始序列大小的内存，在算法过程中用到的额外的存储空间。

一个程序运行所需内存空间的大小，利用程序的空间复杂度可以对程序运行所需要的内存大多少有个预估判断。一个程序的执行除了所需要的存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。

程序执行时所需存储空间包括两部分：

固定部分

这部分空间的大小与输入、输出的数据的个数多少、数值无关，主要包括指令空间(代码空间)、数据空间(常量、变量)等所占用的空间，这部分属于静态空间。

可变空间

这部分空间主要包括动态分配的空间，以及递归栈所需的空间等，这部分的空间大小与算法有关。一个算法所需的存储空间用 f(n) 表示，S(n)=O(f(n))，其中 n 为问题的规模，S(n) 表示空间复杂度。