算法复杂度分为时间复杂度和空间复杂度。时间复杂度是指执行算法所需要的计算工作量，而空间复杂度是指执行这个算法所需要的内存空间。

时间复杂度

一般情况下，算法中基本操作重复执行的次数是问题规模 n 的某个函数，用T(n)表示。若存在函数 f(n)，使得当 n 趋近于无穷大时，T(n) / f(n) 的极限值（当 n 趋近于无穷大时）为非零常数，则称 f(n) 是 T(n) 的同数量级函数。记作 T(n) = O(f(n))，称 O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

随着问题规模 n 的增大，算法执行的时间的增长率和 f(n) 的增长率成正比，所以 f(n) 越小，算法的时间复杂度越低，算法的效率越高。

时间复杂度计算

在计算时间复杂度的时候，首先需要找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同数量级（包括： $1, \log_2n，n，n \log_2n ，n^2，n^3，2^n，n!$ 等），找出后，f(n) = 该数量级，若 T(n) / f(n) 求极限可得到一常数c，则时间复杂度 T(n) = O(f(n))。

$O(1)$ ：常数复杂度（Constant Complexity）

n = 1000
print(n)

$O(log(n))$ ：对数复杂度（Logarithmic Complexity）

i = 1
n = 1000
while i < n:
  print(i)
  i = i * 2 # 终止条件为对数

$O(n)$ ：线性复杂度（Linear Complexity）

n = 1000
for i in range(n):
  print(i)

$O(n^2)$ ：平方复杂度（N Square Complexity）

n = 1000
for i in range(n):
  for j in range(n):
    print(i+j)

$O(n^3)$ ：立方复杂度（N Cube Complexity）

n = 1000
for i in range(n):
  for j in range(n):
    for k in range(n):
      print(i+j+k)

$O(2^n)$ ：指数复杂度（Exponential Growth）

import math

i = 1
n = 1000
while i < math.pow(2,n): # 终止条件为指数
  print(i)

$O(n!)$ ：阶乘复杂度（Factorial Complexity）

i = 1
n = 1000
while i < factorial(n): # 终止条件为指数
  print(i)

def factorial(n):
  if n == 0 or n == 1:
      return 1
  else:
      return (n * factorial(n - 1))

从以上实例中可以简单理解为，时间复杂度就是看代码中复杂度最高部分的运算次数，那么由小到大分别为：
$O(1)<O(log(n))<O(n)<O(n(log(n)))<O(n^2)<O(2^n)<O(n!)$

举一个算法优化的例子，假设我们需要将数字从 1 加到 n，如果使用循环，那么时间复杂度为 $O(n)$ ：

# 硬循环
n = 1000
y = 1 + 2 + 3 + ... + n
# for循环
y = 0
for i in range(n):
  y += i

如果利用等差数列求和公式：n(n + 1) / 2，时间复杂度可以降为 $O(1)$ ：

y = n * (n + 1) / 2

完整公式如下：
$S_n=na_1+\frac{n(n-1)}{2}d,n\in N^*$

其中 $a_1$ 为首项， $a_n$ 为末项， $n$ 为项数， $d$ 为公差， $S_n$ 为前 $n$ 项和。

求解斐波拉契数组（Fibonacci Array）：根据公式 $F_n = F_{n-1} + F_{n-2}$ 每个数字等于前两个数字之和，如：1,1,2,3,5,8,13,21,34,... 求位置为 n 的数字。

递归实现如下：

def fib(n):
  if n == 0 or n == 1:
    return n
  return fib(n - 1) + fib(n - 2)

虽然代码简单但是我们分析一下，它在计算每个位置的数字时，之前的数字都要重新计算一遍，复杂度是呈指数级增长的，所以是 2 的 n 次方的时间复杂度，即 $O(2^n)$ 。

根据主定理（Master Theorem）推断出常用算法的时间复杂度如下：

常用算法	时间复杂度
二分查找（Binary Search）	$O(log(n))$
二叉树查找（Binary Tree Traversal）	$O(n)$
最优有序矩阵查找（Optimal Sorted Matrix Search）	$O(n)$

通用数据结构操作

数组排序算法

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，类似时间复杂度，它也是问题规模 n 的函数，记做 S(n) = O(f(n))。比如直接插入排序（Straight Insertion Sort）的时间复杂度是 $O(n^2)$ ，空间复杂度是 $O(1)$ 。一般的递归算法的空间复杂度是 $O(n)$ ，因为每次递归都要存储返回信息。

时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差。反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差。另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法时，要综合考虑算法的各项性能，包括算法的使用频率、算法处理的数据量的大小、算法描述语言的特性、算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。

参考

https://time.geekbang.org/course/intro/130
https://book.douban.com/subject/3351237/

算法的复杂度

算法的复杂度

时间复杂度

时间复杂度计算

空间复杂度

参考