第二期学习笔记

[fishmwei]

本期学习了复杂度分析的上下两篇文章

[fishmwei]

时间复杂度分析上

为什么需要复杂度分析： 一般通过代码完成之后，再进行时间统计的方法(事后统计法)，受环境影响，受数据规模影响.需要不通过具体的数据来测试，就可以粗略估计出算法的执行效率是最好的。

大O时间复杂度：算法代码执行的时间。代码执行时间随数据规模增长的变化趋势。

// 2n+2 ==> O(n)

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

// 3+n(2+2n) = 2n^2 + 2n + 3 ===> O(n)

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

分析方法：

• 只关注循环执行次数最多的代码
• 加法法则 量级最大的
• 乘法法则 嵌套代码的时间复杂度等于内外代码复杂度的乘积

三个方法可能同时用到，相互融合

复杂度量级

非多项式量级只有两个：O(2^n) 和 O(n!)。
NP

当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。

空间复杂度分析

渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

课后思考题：
性能测试只能测试出当前代码实现方式的性能数据，没有横行对比，只能看出在一定规模的数据下实现是否满足性能要求，不一定是最优解。通过复杂度分析，可以快速获取当前实现的复杂度大O的表示，我们可以通过分析，确定是否可以寻找更优解。估算大数据下，算法的时间与空间消耗。而且，性能测试受当前机器性能或内存影响，不同机器运行结果可能不同，更大数据规模很难通过测试完成或者耗时较长。

[fishmwei]

复杂度分析 下

最好情况时间复杂度（best case time complexity）、最坏情况时间复杂度（worst case time complexity）、平均情况时间复杂度（average case time complexity）、均摊时间复杂度（amortized 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;
  }
  return pos;
}

最好： O(1) 第一个， 最坏 O(n)不存在

平均时间复杂度

发生的概率乘以复杂度， 求和。

加权平均值、即期望值的求法。

均摊时间复杂度

 // array 表示一个长度为 n 的数组
 // 代码中的 array.length 就等于 n
 int[] array = new int[n];
 int count = 0;
 
 void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }

    array[count] = val;
    ++count;
 }

每n个O(1)之后是O(n)， 均摊O(1)

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。

课后思考题：

// 全局变量，大小为 10 的数组 array，长度 len，下标 i。
int array[] = new int[10]; 
int len = 10;
int i = 0;

// 往数组中添加一个元素
void add(int element) {
   if (i >= len) { // 数组空间不够了
     // 重新申请一个 2 倍大小的数组空间
     int new_array[] = new int[len*2];
     // 把原来 array 数组中的数据依次 copy 到 new_array
     for (int j = 0; j < len; ++j) {
       new_array[j] = array[j];
     }
     // new_array 复制给 array，array 现在大小就是 2 倍 len 了
     array = new_array;
     len = 2 * len;
   }
   // 将 element 放到下标为 i 的位置，下标 i 加一
   array[i] = element;
   ++i;
}

最好： O(1)
最坏： O(n)
均摊复杂度 O(1)