时间复杂度 & 空间复杂度简介

时间复杂度

时间复杂度：是一个函数，它定性描述该算法的运行时间，即运行这一算法所需的时间或操作数。通常使用大O表示法表示最糟糕的情形。

详细解析 一般情况下，算法中基本操作重复执行的次数是问题规模 n 的某个函数，用T(n)表示，也称为时间频度，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n))，称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

步骤：

1. 找出算法中的基本语句。（通常是指算法中执行次数最多的语句）
2. 计算基本语句的执行次数的数量级。
3. 用大Ο记号表示算法的时间性能。

💡 例

let sum = 0 // 1次
for (let i = 0; i < n; i++) { // n次
  for (let j = 0; j < n; j++) { // n^2次
    sum ++ // n^2次
  }
}

// 因此有 O(2n^2+n+1)，去除低阶、常数、高阶常参，等到 T(n)=O(n^2).
// 也可以理解为当 n 趋于无穷时，常数的影响已经几乎可以不计。

• 常见的大O运行时间（从快到慢）：
  • O(log n) 对数时间
  • O(n) 线性时间
  • O(n * log n)
  • O(n ^2)
  • O(n!)

空间复杂度：对一个算法在运行过程中临时占用存储空间大小的量度，即算法所耗掉的存储空间。