时间复杂度 vs 空间复杂度

一、时间复杂度

1、是什么

一般情况下，算法中基本操作重复执行的次数是问题规模 n 的某个函数，用 T(n) 表示，若有某个辅助函数 f(n),使得当 n 趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称 f(n) 是 T(n) 的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度，时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。

2、怎么算

(1) 找出算法中的基本语句，一般为最内层循环的循环体

(2) 计算基本语句的执行次数的数量级, 即求出随着 n 的增长，呈现的规律公式

(3) 用「 大O 符号表示法 」，表示时间复杂度

3、常见时间复杂度

• 常数阶 O(1),代码在执行的时候，它消耗的时间并不随着某个变量的增长而增长, 比如下面的语句:

  let i = 1;
  let j = 2;
  ++i;
  j++;
  const m = i + j;

• 对数阶 O($log_2n$),

• 线性阶 O(n), 消耗的时间是随着变量 n 的变化而呈线性变化, 比如一层 for 循环

  for(let i=1; i<=n; ++i){
    j = i;
    j++;
  }

• 线性对数阶 O($nlog_2n$)

• 指数阶：平方阶O($n^2$)

• 立方阶 O($n^3$),…， k次方阶O($n^k$)

• 指数阶 O($2^n$)

• 阶乘 Ο(n!)

随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低

二、空间复杂度

1、是什么

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，用 S(n) 来定义

3、常见空间复杂度

O(1)、O(n)、O(n²)

参考文献:

算法的时间复杂度和空间复杂度-总结
算法的时间与空间复杂度（一看就懂）