什么是时间复杂度？

[qiuhongbingo]

/**
 * 先看一下时间复杂度的概念：
 * 一个算法的时间复杂度反映了程序运行从开始到结束所需要的时间
 * 把算法中基本操作重复执行的次数（频度）作为算法的时间复杂度
 */

/**
 * 但是时间复杂度的计算既可以“有理可依”，又可以靠“主观感觉”。通常我们认为：
 * 没有循环语句，时间复杂度记作 O(1)，我们称为常数阶；
 * 只有一重循环，那么算法的基本操作的执行频度与问题规模 n 呈线性增大关系，记作 O（n），也叫线性阶
 */

/**
 * 那么如何让时间复杂度的计算“有理可依”呢？来看几个原则：
 * 只看循环次数最多的代码
 * 加法法则：总复杂度等于量级最大的那段代码的复杂度
 * 乘法法则：嵌套代码的复杂度等于嵌套内外复杂度的乘积
 */

/**
 * 例子一
 * 执行次数最多的是 for 循环及里面的代码，执行了 n 次，
 * 应该“只看循环次数最多的代码”原则，因此时间复杂度为 O(n)
 */
const cal = n => {
  let sum = 0
  let i = 1
  for (; i <= n; ++i) {
    sum = sum + i
  }
  return sum
}

/**
 * 例子二
 * 分别对 sum1、sum2、sum3 求和：
 * 对于 sum1 求和，循环 100 次，常数执行时间，时间复杂度为 O(1)
 * 对于 sum2 求和，循环规模为 n，时间复杂度为 O(n)
 * 对于 sum3 求和，两层循环，时间复杂度为 O(n²)
 * 因此 O(1) + O(n) + O(n²) 应用加法法则，取三段代码的最大量级，最终的时间复杂度为 O(n²)
 */
const cal = n => {
  let sum1 = 0
  let p = 1
  for (; p < 100; ++p) {
    sum1 = sum1 + p
  }

  let sum2 = 0
  let q = 1
  for (; q < n; ++q) {
    sum2 = sum2 + q
  }

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

  return sum1 + sum2 + sum3
}

/**
 * 例子三
 * 方法 cal 循环里面调用 f 方法，而 f 方法里面也有循环
 * 这时应用“乘法法则”，得到时间复杂度 O(n²)
 */
const cal = n => {
  let ret = 0
  let i = 1
  for (; i < n; ++i) {
    ret = ret + f(i) // 注意  f(i)
  }
}

const f = n => {
  let sum = 0
  let i = 1
  for (; i < n; ++i) {
    sum = sum + i
  }
  return sum
}

/**
 * 例子四
 * 再看一个对数阶的概念
 * 这里的不同之处是 aFun 每次循环，i = i * 2，那么自然不再是全遍历
 * 我们只要知道 x 值是多少，就知道这行代码执行的次数了，通过 2x = n 求解 x
 * 数学中求解得 x = log2n 即时间复杂度为 O(log2n)
 */
const aFun = n => {
  let i = 1
  while (i <= n) {
    i = i * 2
  }
  return i
}

const cal = n => {
  let sum = 0
  for (let i = 1; i <= n; ++i) {
    sum = sum + aFun(n)
  }
  return sum
}

/**
 * 例子五
 * 关于最好时间复杂度、最坏时间复杂度
 * 这个代码有一层循环，循环规模和 n 成线性关系。因此时间复杂度为 O(n)
 */
const find = (array, x) => {
  let pos = -1
  let n = array.length
  for (let i = 0; i < n; ++i) {
    if (array[i] === x) {
      pos = i
    }
  }
  return pos
}
/**
 * 我们改动代码：在找到第一个匹配元素后，循环终止，那么时间复杂度就不一定是 O(n) 了
 * 因此就有了最好时间复杂度、最坏时间复杂度的区别
 * 所以这段代码最好时间复杂度就是 O(1)、最坏时间复杂度还是 O(n)
 */
const find = (array, x) => {
  let pos = -1
  let n = array.length
  for (let i = 0; i < n; ++i) {
    if (array[i] === x) {
      pos = i
      break
    }
  }
  return pos
}

/**
 * 总结：由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势
 * 因而常量、低阶、系数实际上对这种增长趋势不产生决定性影响，所以在做时间复杂度分析时忽略这些项
 * 常见时间复杂度：
 * O(1)：基本运算 +、-、*、/、%、寻址
 * O(logn)：二分查找，跟分治（Divide & Conquer）相关的基本上都是 logn
 * O(n)：线性查找
 * O(nlogn)：归并排序，快速排序的期望复杂度，基于比较排序的算法下界
 * O(n²)：冒泡排序，插入排序，朴素最近点对
 * O(n³)：Floyd 最短路，普通矩阵乘法
 * O(2ⁿ)：枚举全部子集
 * O(n!)：枚举全排列
 */