算法复杂度分析

之前写过一篇文章“不要陷入技术的魔咒”，然而最近又迷上了写拓展，我TM！！！管不住自己，之前我哥推荐了很好的git管理工具，很多东西都用那个托管了，真的很少在写博客了，直话直说我c++这还是学的非常差的，当然后面也没有好好学过，自从开始写一些脚本开始，我更加意识到了自己的软肋，虽然我浑身都是软肋，陈sir，每次气的每次都说我该回炉重造。的确我非常有必要回炉重造了，客观来看我底子的确是弱得很，以后尽量希望明确学习方向，不在对一些应用场景少、难以产生效益、无法应用到实际项目、瞎折腾的技术进行钻研。重最简单的开始学习吧，之前，这个博客是我建的第一个博客，之前也想换换托管方式，打算在阿里云上托管的，但转念一想。又觉得不是很有必要，之前也试过阿里云oss。不过我感觉git+github pages+hexo这个已经完全够用了。也懒得再折腾。

其次c++已经鸽了有大半年了，所以有必要重hello world，重新开始学的必要，我感觉，

算法复杂度以及渐进复杂度

一个问题往往可以以效率不同的算法来解决，当然在数据较少的时候，各种算法之间的差异也许微不足道，但当数据量成倍增加时，你就会发现不同算法之间的差异非常非常明显，如果你关注LeetCode你会发现不同的算法在占用和时间上会有非常明显的差别，比如一道题，你用双指针可能只需要4ms，其他的算法可能是他的一百多倍。为了比较算法的效率，两个名字很复杂的老外，引入了一种称为计算复杂度的标准来衡量算法。计算复杂度表示一种算法需要付出多大的成本和努力，当然成本在很多不同的地方有自己的衡量标准，我们常说的衡量效率就是时间和空间，当然远远不止这两种，其他，其他我也不知道啊！！！当然时间因数往往比空间因素重要的多，我们往往关注的是数据处理的时间，而不是空间，毕竟现在在技术层面，数据储存完全不是人们担心的地方，而时间和效率往往决定这一个程序的好坏。印度是全世界最大的代码输出国，微软ceo也是印度人，印度人写代码哪管那么多啊，所以是现在硬件的发展完全可以弥补算法层面的不住，当然这只是在某些领域，在一些非常需要算法效率的领域，你，如果，不会写算法还是删库趁早跑路吧，我觉得你进公司面试可能面试官就直接吧你pass了

评估算法效率

算法效率的评估并不能以时间来评估，而是采用某种逻辑关系，用文件和数组的尺度n同时间t之间的关系，我们该如何表示不同的t和n之间的关系呢，

假如t和n之间是线性关系

$$n2=5n1 则必有t2=5t1$$

同样

t1=log2(n)，t2=log2(2n)则t1=t2+1 $$ {log2} 当然通常情况下。，这些n与t之间的关系复杂的多的多。当数据量非常巨大的时候，计算这些函数才变得比较重要，不会实质上改变函数数量级的应该从函数中剔除，emmmmm就相当于数学的极限思想。比如说f（n）=n+10000，在n足够大时我们就没有必要考虑常数项。 ## 大O表示法 这大概是最长用来表示渐进复杂度（评估函数的增长率）的表示方法了，是Paul Bachmann引入的 具体我就不说了详情请看百科 [请点我！！！！](https://baike.baidu.com/item/大O表示法/1851162?fr=aladdin) ## 常见的时间复杂度量级 我们先从常见的时间复杂度量级进行大O的理解： - 常数阶O(1) - 线性阶O(n) - 平方阶O(n²) - 对数阶O(logn) - 线性对数阶O(nlogn)  ### O(1)  [^]: 图片转载至掘金 无论代码执行了多少行，其他区域不会影响到操作，这个代码的时间复杂度都是O(1)

void swapTwoInts(int &a, int &b){
  int temp = a;
  a = b;
  b = temp;
}

### O(n)  在下面这段代码，for循环里面的代码会执行 n 遍，因此它消耗的时间是随着 n 的变化而变化的，因此可以用O(n)来表示它的时间复杂度。

int sum ( int n ){
   int ret = 0;
   for ( int i = 0 ; i <= n ; i ++){
      ret += i;
   }
   return ret;
}

特别一提的是 c * O(n) 中的 c 可能小于 1 ，比如下面这段代码：

void reverse ( string &s ) {
    int n = s.size();
    for (int i = 0 ; i < n/2 ; i++){
      swap ( s[i] , s[n-1-i]);
    }
}

### O(n²)  当存在双重循环的时候，即把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。

void selectionSort(int arr[],int n){
   for(int i = 0; i < n ; i++){
     int minIndex = i;
     for (int j = i + 1; j < n ; j++ )
       if (arr[j] < arr[minIndex])
           minIndex = j;
       
     swap ( arr[i], arr[minIndex]);
   }
}

这里简单的推导一下 - 当 i = 0 时，第二重循环需要运行 (n - 1) 次 - 当 i = 1 时，第二重循环需要运行 (n - 2) 次 - 。。。。。。 不难得到公式：

(n - 1) + (n - 2) + (n - 3) + ... + 0
= (0 + n - 1) * n / 2
= O (n ^2)

当然并不是所有的双重循环都是 O(n²)，比如下面这段输出 30n 次 `youmingsama：）`的代码。

void printInformation (int n ){
   for (int i = 1 ; i <= n ; i++)
        for (int j = 1 ; j <= 30 ; j ++)
           cout<< "youmingsama：）"<< endl;
}

### O(logn) 

int binarySearch( int arr[], int n , int target){
  int l = 0, r = n - 1;
  while ( l <= r) {
    int mid = l + (r - l) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] > target ) r = mid - 1;
    else l = mid + 1;
  }
  return -1;
}

在二分查找法的代码中，通过while循环，成 2 倍数的缩减搜索范围，也就是说需要经过 log2^n 次即可跳出循环。 同样的还有下面两段代码也是 O(logn) 级别的时间复杂度。

  // 整形转成字符串
  string intToString ( int num ){
   string s = "";
   // n 经过几次“除以10”的操作后，等于0
   while (num ){
    s += '0' + num%10;
    num /= 10;
   }
   reverse(s)
   return s;
  }

void hello (int n ) {
   // n 除以几次 2 到 1
   for ( int sz = 1; sz < n ; sz += sz) 
     for (int i = 1; i < n; i++)
        cout<< "youmingsama：）"<< endl;
}

### O(nlogn) 将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logn)，也就是了O(nlogn)。

void hello (){
  for( m = 1 ; m < n ; m++){
    i = 1;
    while( i < n ){
        i = i * 2;
    }
   }
}

## 最好，平均和最坏情况 ### 先举个栗子 分析以下这段代码的时间复杂度

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

#### 分析 - 功能：在一个无序数组array中，查找变量x出现的位置 - 时间复杂度：`O(n)`, n表示数组的长度 更为优化的方式

// 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(n)了，不同情况下这段代码的时间复杂度是不同的。 ### 引入概念 - 最好情况时间复杂度：在最理想情况下，执行代码的时间复杂度 - 最坏情况时间复杂度：在最糟糕情况下，执行代码的时间复杂度 - 平均情况时间复杂度：最好情况和最坏情况都是属于极端情况，发生的概率并不大。需要表示平均情况下的复杂度 ### 如何分析平均情况时间复杂度 以上面的例子为例：查找x在数组中的位置，有`n+1`种情况，在数组`0~n-1`的位置上和不在数组中。 将每种情况下，查找需要遍历的元素个数相加，再除以n+1种情况，就可得到需要遍历的元素个数的平均值 `(1+2+3+...+n+n)/n+1 = n (n+3) /2(n+1)` 省略掉系数、低阶、常量后得到平均时间复杂度为`O(n)` #### 存在问题 在以上的n+1种情况中，未考虑x在每种情况下出现的概率。 现在假设，x在数组中与x不在数组中的概率各为`1/2`； 要查找的x出现在`0~n-1`这n个位置的可能性是相同的，即`1/n`； 那么，要查找的x出现在`0~n-1`中任意位置的概率为 `1/2*1/n = 1/(2n)` 将每种情况发生的概率考虑进去后，平均时间复杂度计算过程变成：

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

作期望值。因而平均时间复杂度的全称为**加权平均时间复杂度**或**期望时间复杂度**。 > 注：很多时候，我们只使用一个复杂度就可以满足要求。只有同一块代码在不同情况下，时间复杂度有量级的差距，才会使用以上3种复杂度的表示法来区分。 ### 均摊时间复杂度、摊还分析（摊销分析） 举栗子说明：

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

#### 分析 - 功能：实现了往数组中插入数据的功能。 - 具体： 1 . 当数组满了`count == array.length`,就用for循环遍历求和，将求得的和放在数组的第一个位置，并清空数组其余元素；然后再插入新的元素。 2 . 当数组一开始就有空闲，则直接将数据插入数组。 - 复杂度分析： 1 . 最好情况：数组中有空闲，直接将数据插入到`count`的位置，为`O(1)` 2 . 最坏情况：数组没有空闲空间，需要先做一个遍历求和，再作插入。所以复杂度为`O(n)` 3 . 平均时间复杂度：`O(1)` ##### 平均时间复杂度如何得到 总共`n+1`种情况，前`n`中情况每种时间复杂度都为`O(1)`，后一种情况时间复杂度为`O(n)`；`n+1`种情况发生的概率一样，为`1/(n+1)`；根据加权平均计算方法： >

1*1/(n+1) + 1*1/(n+1) + ... + n*1/(n+1) = O(1)

#### 摊销时间复杂度（amortized time complexity） 分析发现: 1 . `insert()`函数在**大部分情况**下，时间复杂度都为`O(1)`；**极个别情况**下，复杂度才高，为`O(n)` 2 . `insert()`函数中，`O(1)`时间复杂度的插入和`O(n)`时间复杂度的插入，**出现频率很有规律**。存在前后时序关系，一般一个`O(n)`插入之后，紧跟着`n-1`个`O(1)`的插入操作，循环往复。 ##### 针对这种场景，引入均摊分析法 大致思路：每一次 `O(n)` 的插入操作，都会跟着 `n-1` 次 `O(1)` 的插入操作，所以把耗时多的那次操作均摊到接下来的 `n-1` 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 `O(1)`。 #### 总结 对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。 而且，**在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度**。 > 均摊时间复杂度就是一种特殊的平均时间复杂度，没必要花太多精力去区分它们。 ## NP完整性 决定性算法，，，，，，emmmmmmm这个好难，看不太懂，暂时就鸽了吧。就酱