✨[算法] 复杂度分析

• 如何分析、统计算法的执行效率和资源消耗？
• 为什么有最好、最坏、平均、均摊时间复杂度？

O(f(n))表示运行算法所需要执行的指令书， 和f(n)成正比。 O()表示算法执行的最低上界， 学术中表示上界

• T(n) = O(x), 渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。O(1) < O(logn) < O(n) < O(nlogn) < O(n2 )
  1. 只关注循环执行次数最多的一段代码
  2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
  3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

• S(x) 渐进空间复杂度, 表示算法的存储空间与数据规模之间的增长关系。O(1)、O(n)、O(n^2) NP, Non-Deterministic Polynomial, 当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。
  O(logn)， 在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))。

  i=1; while (i <= n) { i = i * 2; } // 1, 2, 4...2^x = n; 以2为底n的倍数

  O(nlogn)， 时间复杂度是 O(logn)，循环执行 n 遍。

  for (; j < n; ++j) { while (i <= n) { i = i * 2; } }
  

  O(m+n)， 复杂度由两个数据的规模来决定。

  for (; i < m; ++i) { sum_1 = sum_1 + i; } for (; j < n; ++j) { sum_2 = sum_2 + j; }
  

  O(m*n),

  for (; i < m; ++i) { for (; j < n; ++j) { // todo } }
  

• 最好情况时间复杂度, 在最理想的情况下，执行这段代码的时间复杂度

• 最坏情况时间复杂度, 在最糟糕的情况下，执行这段代码的时间复杂度
• 平均情况时间复杂度, 加权平均时间复杂度或者期望时间复杂度。
• 均摊时间复杂度(平摊分析), 将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。一般均摊时间复杂度就等于最好情况时间复杂度。