时间复杂度浅析

title: 时间复杂度浅析 id: 9239f73c1998f3f1bfef4cca286fa2e8 tags: [] date: 2000/01/01 00:00:00 updated: 2021/03/01 17:32:18 isPublic: true --#|[分隔]|#--

时间复杂度浅析

最近在做算法题，发现时间复杂度对算法的影响，意识到这一课不能再拖了，得补上。

• 每个方法都有自己的时间复杂度，但只有这个方法的参数，参与了方法内的循环时，它的时间复杂度才有意义。

• 没有入参或者入参没有参加方法内的循环时，这个方法时间复杂度固定为1，表示入参不会影响这个方法执行的时间

• 时间复杂度是个式子，是一个用入参n表示的式子

• 时间复杂度表示的是，当入参n变化，这个方法内部变化的趋势，比如式子n和n^2，前者随着n变大，花费的时间等比增加，后者则是随着n增大，花费时间以更陡峭的趋势增加。

• O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

• 时间复杂度只是表示方法内部复杂程度随入参n的变化趋势，不代表方法的优劣，比如n的比较小时，O(n^n)可能比O(1)更节省资源，这需要看方法内部的处理。

方法的时间复杂度是个式子，数学上叫做函数，用T(n)表示，n就是这个方法参数，就好比这个简单的数学公式：f(x) = 2x + 1，在这里f就是T，x就是n。

f的表达式是2x + 1，时间复杂度的求解，就是分析js方法体，得出T的表达式了。

T的表达式，一般写作T(n) = O(「式子」)（大O表示法），关键就是里面的「式子」，下面就来说明这个式子如何得出了。

推导

常数级

分析下面这个方法：

function temp(n) {
  let a = n // 执行1次
  let b = 2 * n // 执行1次
}

这个方法的时间复杂度为O(1)。

里面一共两条语句，而且没有循环、递归等等，只是简单的两条语句，所以这个方法的虽然传入了n，但代码执行次数固定为常数2，和n无关，所以时间复杂度为O(2)，但时间复杂度表示的是一个趋势，2是一个固定的常量，表达不了趋势，所以这里统一写成1，也就是O(1)。

线性级

分析下面这个方法：

function temp(n) {
  let a = n // 执行1次
  let b = 2 * n // 执行1次
  for (let i = 0; i < n; i++) {
	  a = a * a // 执行n次
	  b = b * b // 执行n次
  }
}

这个方法的时间复杂度为O(n)。

正常理解，这个式子应为1 + 1 + n + n => 2 + 2n，但仍然是那句话，时间复杂度表示的是一个趋势，常数是没有意义的，所以2 + 2n可以简写为2n。

但其实，2n还是3n还是100n，对趋势并没有影响，他都是线性函数，随着入参n的变化，这个方法的复杂度还是等比变化的，所以2n可以进一步简写成n，最后就是O(n)。

指数级

分析下面这个方法：

function temp(n) {
  let a = n // 执行1次
  let b = 2 * n // 执行1次
  for (let i = 0; i < n; i++) {
	  a = a * a // 执行n次
	  b = b * b // 执行n次
	  for (let j = 0; j < n; i++) {
		  a = a * a // 执行n * n次
		  b = b * b // 执行n * n次
	  }
  }
}

这个方法的时间复杂度为O(n^2)。

正常理解，这个式子应为1 + 1 + n + n + n * n + n * n => 2 + 2n + 2n^2 => n + n^2，但其实和n^2相比，n存在的意义几乎可以忽略，n^2才控制了主要的趋势的走势，n实在是可有可无，所以这里可以简写为n^2，用大O表示法就是O(n^2)

对数级

分析下面这个方法：

function temp(n) {
  for (let i = 0; i < n; i = i * 2) {
	  a = a * a // 执行了x次（以2为底，n的对数，比如n = 2, 则 x = 1; n = 4, 则 x = 2, x = 8, 则 x = 3）
  }
}

这个方法的时间复杂度为O(logn)。

注意这个方法中的for循环，里面i的递增并不是加1，而是乘2，x是以2为底n的对数，也就是说，2的x次方等于n。

而且，i的递增无论是乘几，哪怕是3、4...100，时间复杂度都写做O(logn)，这里的底，其实就类似于2n中的2，可以忽略掉。

总结

时间复杂度除了上述几种类型，还有很多其他类别，优劣排序为：

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

虽然一个方法有时间复杂度，但并不是说时间复杂度低的就一定好，当n比较小时，O(n^n)可能比O(1)更节省资源，这都需要看函数内部具体的指令了。