时间复杂度

为什么需要 时间复杂度分析

如果 将程序跑一遍,通过统计/监控 得到算法执行的时间和占用的内存(事后统计法)

这样做得到得数据

1.受测试环境影响 2.受数据规模的影响很大

大O复杂度表示法

假设每行代码执行时间一致,每行执行一次为 1个unit_time

int cal(int n) {
  int sum = 0;
  int i = 1;
  int j = 1;
  for (; i <= n; ++i) {
    j = 1;
    for (; j <= n; ++j) {
      sum = sum +  i * j;
    }
  }
}

第 2/3/4 每行 1个unit_time, 5/6 行 n个, 7/8 行 n²个,
执行时间 T(n) = (2n² + 2n + 3) * unit_time

大O 时间复杂度,也称为 渐进式时间复杂度,表示 代码执行时间 随数据规模增长 的变化趋势

当n趋近无穷大,公式中的 低阶 常量 系数 将不影响左右增长趋势,而可以被忽略.

T(n)=O(f(n)),最终,上述代码的 大O时间复杂度 被记为 T(n) = O(n²)

T(n) 总执行时间, F(n) 每行代码总执行次数

时间复杂度分析规则

一段代码

1.只关注循环执行次数最多的一段代码

2.总的时间复杂度就等于量级最大的那段代码的时间复杂度

时间复杂度分析规则类别

最好/最坏时间复杂度:在最理想/最糟糕 的情况下的时间复杂度
(best/worst case time complexity)
平均情况时间复杂度:在平均 的情况下的时间复杂度
(average case time complexity)
加权平均时间复杂度/期望时间复杂度:计算 平均情况时间复杂度 时,加入了概率权重

// n表示数组array的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}
// 最好/最坏: O(1),O(n)
// 平均:     元素在0~k~n-1中,需要执行k次,元素在n或不在数组中,需要执行n次,
//           总计n+1种情况,共执行1+2+3...+n+n= n(n+3)/2 次,
//           平均 n(n+3)/2(n+1) 次
// 加权平均: 增加考虑每种情况出现概率权重,
//          假设 1/2 不在数组中,则出现在数组中每个位置概率为w = 1/2n,
//          执行次数为 (1+2+3...+n)*w + n*1/2 = (3n+1)/4

均摊时间复杂度:摊还分析/平摊分析,针对存在规律的 平均情况时间复杂度
的一种分析思想
(amortized case time complexity)

例如 每一次O(n)的操作,会紧跟着n-1次O(1)的操作,将O(n)均摊在n-1次的O(1)上,最终 时间复杂度为O(1)

常见复杂度量级

常数阶O(1)　　 字典查找、数组索引

对数阶O(logN)　　 二分查找

线性阶O(n) 循环

线性对数阶O(nlogn) 循环+分而治之

平方阶O(n²)　　 双重循环

立方阶O(n³) 多重循环

K次方阶O(n^k)

指数阶(2^n)

// logN 对数阶示例
i = 1;
while (i <= n)  {
    i = i * 2;
}

空间复杂度,O(1),O(n),O(n²),表示 算法的储存空间 与数据规模之间 的增长关系