二、时间复杂度

（一）含义

• $O()$ 读作 Big O
• 评估一个算法在最坏情况下的计算数量级别
• 如果一个算法所有操作数量级和为 $aN^2+bN+c$
  • 则该算法的时间复杂度为 $O(N^2)$
• 常数操作：一个操作和样本的数据量无关，每次都是固定时间完成

（二）master 公式

1.含义

• 用于估算递归算法的时间复杂度

$T(N) = aT(\frac {N} {b}) + O(N^d)$

符号	含义	解释
$T(N)$	母问题的数量规模	第一次递归的数组长度
$a$	子问题递归的次数	递归了多少次
$T(\frac {N} {b})$	子问题的数量规模，等量	每一次递归后分解出来的子数组长度
$O(N^d)$	除递归外的常数操作	算法中求某个值、返回某个值、判断某个值等操作

2.应用示例

• 二分法求数组中的最小值
• 母问题：求数组中的最小值
• 子问题：求数组的一半区域中的最小值

const arr = [3, 5, 4, 2, 6, 7, 1, 8];

const getMin = (arr, L, R) => {
  if (L === R) return arr[L];

  /**
   * 求中点
   * 相比于 min = (R + L) / 2 更优，L、R过大时不会有溢出风险
   * >> 1 相当于 / 2
   */
  let mid = L + ((R - L) >> 1);

  return Math.min(getMin(arr, L, mid), getMin(arr, mid + 1, R));
};

console.log(getMin(arr, 0, arr.length - 1)); // 1

• $T(N) = 2 \times T(\frac {N} {2}) + O(1)$
  • a = 2，左右两部分，共调用了两次子问题
  • b = 2，每一次分两半，子问题规模为原数组的一半
  • d = 0，常数操作 $O(1)$
• 如果 $\log_{b}{a} < d$ ，则 $O(N^d)$
• 如果 $\log_{b}{a} > d$ ，则 $O(N^{\log_{b}{a}})$
• 如果 $\log_{b}{a} = d$ ，则 $O(N^d \times \log_{2}{N})$