算法系列（一）深入理解算法时间复杂度、空间复杂度

原文地址 https://www.heayan.com/articles/2018/03/01/1519872741994.html

前言

时间复杂度、空间复杂度、稳定性是算法使用是主要考虑的三个因素。这三个因素，决定了程序执行是的性能好坏。时间复杂度，就是对算法耗时的一种评估。空间复杂度，就是对算法内存占用的一种评估。稳定性，就是对算法整体耗时、内存占用的幅度的一种评估。任何一种算法是存在天然缺陷的，我们需要根据不同的应用场景，选择合适的算法。下面针对时间复杂度、空间复杂度、稳定性做一个总结。

时间复杂度

首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模 n 的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度 T(n)=O(f(n))简称为时间复杂度，其中的 f(n)一般是算法中频度最大的语句频度。此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。

• 常见的算法时间复杂度由小到大依次为：
  Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

求解算法的时间复杂度的具体步骤是：

1. 找出算法中的基本语句
   算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

2. 计算基本语句的执行次数的数量级
   只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。

3. 用大 Ο 记号表示算法的时间性能
   将基本语句执行次数的数量级放入大 Ο 记号中。

下面举个栗子：
如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。

  int x=0;
  for (int k=1; k<=n; k++){
	x++;
  }　　
  for (int i=1; i<=n; i++){
	for (int j=1; j<=n; j++){
	  x++;
	}
  }　　

int x=0 时间复杂度 Ο(1),第一个 x++ 时间复杂度为 Ο(n)，第二个 x++ 时间复杂度为 Ο(n2)，则整个算法的时间复杂度为 Ο(1+n+n2)=Ο(n2)。

再举个栗子：

  int num1=1;
  int num2=1;
  for (int k=1; k<=n; k++){
	num1 += k;
  }　　
  for (int i=1; i<=n; i++){
	for (int j=1; j<=n; j*=2){
	  num2 += j;
	}
  }

int num1=1 的时间复杂度为 Ο(1),int num2=1 的时间复杂度为 Ο(1)，num1+=k 的时间复杂度为 Ο(n),num2+=j 时间复杂度为 nlog2n（n 乘以以 2 为底 n 的对数）
其他语句的时间复杂度为 Ο(1),则整个算法的时间复杂度为 Ο(1+1+n+nlog2n)=Ο(nlog2n)。

Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是 Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和 Ο(n3)称为多项式时间，而 Ο(2n)和 Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法，把这类问题称为 P 类问题，而把后者称为 NP 问题。这只能基本的计算时间复杂度，具体的运行还会与硬件有关。

空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做 S(n)=O(f(n))。比如直接插入排序的时间复杂度是 O(n^2),空间复杂度是 O(1) 。而一般的递归算法就要有 O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术。

算法执行期间所需要的存储空间包括 3 个部分：

1. 算法程序占用的空间
2. 输入数据占用的存储空间
3. 辅助变量占用的空间

举个栗子：

int x=0;
for (int k=1; k<=n; k++){
  x++;
}　　
for (int i=1; i<=n; i++){
  for (int j=1; j<=n; j++){
	x++;
  }
}　　

int x=0 空间复杂度为 Ο(1)，int k=1 空间复杂度为 Ο(1)，int i=1 空间复杂度为 Ο(1)，int j=1 空间复杂度为 Ο(1)，整个算法空间复杂度为 Ο(1+1+1+1)=Ο(1)。

常见算法对比

版权声明：版权所有，转载请注明原文地址。