Skip to content

Latest commit

 

History

History
150 lines (108 loc) · 4.18 KB

complexity.md

File metadata and controls

150 lines (108 loc) · 4.18 KB
Raw

复杂度

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

提高代码性能的办法：一个是执行的时间，一个是占用的内存空间，所以算法上讲

  • 时间复杂度
  • 空间复杂度

复杂度是在临界条件下对代码执行效率的评判，只是一个粗略的估计，公式为：

T(n) = O(f(n))

其中，T 是指时间频度，n 是指问题的规模，O 是指复杂度，f 是描述代码在临界情况下的执行时间之和的辅助函数。

一段代码的执行时间频度可能不同，但复杂度是相同的，例如，T(n) = n2+3n+4 与 T(n) = 4n2+2n+1 它们的频度不同，但时间复杂度相同，都为 O(n2)。因为当问题的规模无限大时，低阶数、常数项基本可以被忽略了。

衡量一个算法的优缺，抛开环境因素最好的方法就是用复杂度来衡量。对于一个算法，我们常见的复杂度表示的属性有：

  • 最好
  • 平均值
  • 最差
  • 占用内存
  • 是否稳定

一般情况下，我们说某段代码的复杂度都是指的最坏的情况。

如何分析时间复杂度

常见的时间复杂度有

  • 常数阶 O(1)
  • 对数阶 O(logn) 一般讨论的是 2 的对数，实际情况常数皆可
  • 线性阶 O(n)
  • 线性对数阶 O(nlogn)
  • 平方阶 O(n^2)
  • 指数阶 O(2^n)

分析一段代码的复杂度所依据的规则：

  • 只关注循环执行次数最多的一段代码 
    for (...)
  for (...)
    for(...)
      x += 1 // 只关注这里的语句
  • 加法原则：总复杂度等于量级最大的那段代码的复杂度。用公式表示即为 
    T1(n) = O(f(m))
T2(n) = O(g(n))
T1(n) + T2(m) = O(max(f(n), g(m)))
  • 乘法原则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。用公式表示即为 
    T1(n) = O(f(m))
T2(n) = O(g(n))
T1(n) * T2(m) = O(f(n) * g(m))

栗子🌰

在代码的执行过程中，每一个表达式、判断、循环等的执行所花费的时间为一个 unit_time ，这个时间是依赖执行环境的，但我们可以粗略的表示。

其中，当在极限情况下执行每行语句时，时间频度可以抽象为代码的执行次数。

常数阶 O(1)

let i = 0
for (; i < 1000; i++) {
  console.log(i)
}

时间频度 T(n) = (1 + 1 + 1000) unit_time，虽然循环了 1000 次，但复杂度仍为常数阶 O(1002)

对数阶 O(logn)

let i = 1
let n = 100
while (i < n) {
  i *= 3
}

当 n = 100 时，循环的次数为

3^x < 100
x = log3(100)

时间频度 T(n) = 1 + 1 + log3(100) + log3(100)，当 n 无限大时，复杂度为 O(log3(n))

线性阶 O(n)

线性阶比较好理解，只要存在单层循环，当 n 无限大时，去掉低阶常数项，复杂度即为 O(n)

线性对数阶 O(nlogn)

想当然，在对数阶的外层套一层循环，它的复杂度即为 O(nlogn)

let n = 100
for (let i = 0; i < n; i ++) {
  let j = 1
  while (j < n) {
    j *= 2
  }
}

上面的复杂度为 O(nlog2(n))

平方阶 O(n^2)

想当然，嵌套的循环

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    console.log('')
  }
}

for (let k = 0; k < n; k++) {
  console.log('')
}

根据加法规则，上面代码的复杂度依旧为 O(n^2)

指数阶 O(2^n)

无

如何分析空间复杂度

无

链接