好玩的网站列表

1. 为什么需要复杂度分析？

通过统计和监控得到的算法执行时间的占用的内存的大小的方法称为事后统计法，这种方法有其局限性：

• 测试结果非常依赖于测试环境
• 测试结果受数据规模的影响很大, 而且会和数据集本身的数据质量有关
• —-> 因此我们需要一个不用具体的测试数据来测试，就可以粗略估计算法的执行效率的方法

2. 大O复杂度表示法

• 假定每行代码执行时间都一样
• 并不表示具体的代码执行时间，而是表示执行时间随着数据规模增大的变化趋势，因此也叫做渐进时间复杂度。

3. 如何分析代码的时间复杂度

• 只关注循环执行次数最多的一段代码
• 加法原则：总复杂度等于量级最大的那段代码的复杂度
• 乘法法则： 嵌套代码的复杂度等于签到内外层代码复杂度的乘积

4. 复杂度量级

• 常量阶 O(1)
• 对数阶 O(logn)
• 线性阶 O(n)
  • O (m+n) 当我们不知道几个变量的大小的时候
• 线性对数阶 O(nlogn)
• 平方阶 O(n^2)
  • O (m*n) 乘法关系，不知道参量之间的相对大小
• k次方阶 O(n^k)
• 指数阶 O(2^n)
• 阶乘阶 O(n!)

5. 空间复杂度分析

空间复杂度的全程是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。

大O时间复杂度，并不具体表示代码真正的执行时间，而是表示代码执行时间随着数据规模的增大的变化趋势。因此也叫做渐进时间复杂度，(asymptotic time complexity)

T(n) = O(f(n))

T(n) - 代码的执行时间
n - 数据规模的大小
f(n) - 每行代码执行的次数总和
O - 表示左右成正比

5.1 Tips

• 只关注循环执行次数最多的一段代码
• 总复杂度等于量级最大的那段代码的复杂度
• 嵌套代码的复杂度为嵌套内外代码复杂度的乘积

6. 复杂度的分析

6.1 时间复杂度分析

6.1.1 多项式量级

• O(1)
  • 常量级的代码，我们将其时间复杂度都记作O(1)
• O(logn)

 i=1;
 while (i <= n)  {
   i = i * 2;
 }

• O(nlogn)
• O(m+n)
• O(m*n)

6.1.2 非多项式量级

非常低效，会随着n的增长急剧增长，因此我们应当尽量不选择有如下时间复杂度的算法

• O(2^n)
• O(n!)

6.2 空间复杂度分析

渐进空间复杂度，表示算法的存储空间和数据规模之间的增长关系。

一般来说在O(1), O(n), O(n^2)这几个可能性上面

7. 浅析最好、最坏、平均、均摊时间复杂度

// 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;
}

7.1 最好情况时间复杂度(best case time complexity)

上面这段代码，最好情况是O(1)

7.2 最坏情况时间复杂度(worst case time complexity)

上面这段代码，最坏情况是O(n)

7.3 平均情况时间复杂度(average case time complexity)

需要算上发生的概率

上述例子当中，因为要查找变量x在数组当中的位置，一共有n+1种情况，在数组的0 - n-1位置中和不在数组当中。将每种情况下，需要遍历的元素个数累加起来，再除以n+1,就可以得到需要遍历的元素个数的平均值了

即

(1+2+3+ ... + n + n) / (n+1) = n(n+3)/(2(n+1))

故平均复杂度还是O(n)

然而还要考虑每种情况下 发生的概率实质上是不同的，需要将这个算上

7.4 均摊时间复杂度(amortized time complexity)

不是遍历case，而是有轮回的，因此算一个轮回里的时间就可以得出平均复杂度了

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 stone2paul@gmail.com