算法思想（一）理解复杂度

深藏阁楼爱情的钟 2021-12-24 15:57 219阅读 0赞

--------------------

> 本来是想出两个系列，一个算法题解，一个算法思想，但是讲思想必须用到题目，题目里也必然蕴含思想，不如两者合并hiahiahia~~

## 本节要点： ##

*  时间复杂度与空间复杂度是互补的
 *  时间复杂度的内容、估计与大小比较
 *  ## 时间复杂度 ##
 *  指时间随着计算量增大而增大的速度，时间复杂度是计算量的函数
 *  常见时间复杂度：从小到大
    
     *  O(1)
     *  O(n)
     *  O(n\*logn)
     *  O(n\\(^2\\))
     *  O(n\\(^3\\))//以上，多项式时间；以下，指数时间
     *  O(2\\(^n\\))
     *  O(n!)
 *  复杂度均可以用包含n的多项式表达，称为多项式时间。  
    此外常见复杂度还有O(2^n)和O(n!)等，称为指数时间。

> 我决定不写NP问题那些信仰一样的瞎\*\*扯的东西?

## 空间复杂度 ##

*  指程序占用的空间大小，一般来说，对同一个需求，时间复杂度越大，空间复杂度越小，即时间空间是互补的。但是一般编程时对时间复杂度最关心。

## 如何估计时间复杂度 ##

1.  默认估算最坏情况下的时间复杂度
2.  加法：多个循环或分支结构之间采用加法
3.  乘法：循环嵌套使用乘法
4.  分支结构：多分支中选择时间复杂度最大的分支

--------------------

# 举个例子 #

![lizi][]

### 题目文本 ###

给出一个长度为n的数列A1，A2，…，An，求最大连续和。
    换句话说，要求找到1≤i≤j≤n，使得Ai + Ai+1 + … + Aj尽量大。

> 这里有多种不同复杂度的方法

### 暴力穷举O(n^3) ###

> 两个循环确定被计算的子序列的两端，一个循环用来计算子序列的和，不断比较和的大小。懒得写代码了。

### 数组辅助O(n^2) ###

> 将计算的和放到数组中，可以有效避免重复计算

#include <iostream>
    #include <stdlib.h>
    using namespace std;
    
    int main(){
    
        /*初始化各种需要的变量*/
        int num;
        cin >> num;         //输入被计算的数组的大小
        int A[num];        //初始化被计算的数组A
        for(int i=0;i<num;i++){
            A[i]=rand();
        }
        
        /*计算前n项和*/
        int S[num]={0};    //储存A数组的前n项和。
        S[0] = 0;           //前0项和当然为0
        for(int i =1;i<=num; i++){
            S[i]=S[i-1]+A[i];
        }
    
        /**/
        int best = A[1];
        for(int i=1;i<= num; i++)
            for(int j =  i;j<= num;  j++ )
                best =  max (best ,  S[j] - S[i-1]) ;
        }
    
        cout<<best<<endl;
        return 0;
    }

### 二分法O(n\*logn) ###

> 一般用二分法的算法复杂度都是O(n\*logn)

待补充，反正只需要知道二分法的复杂度是O(n*logn)就行了?

### 更nb的数组辅助O(n^2) ###

> 继承方法2的思想，要想获得最大连续和`Sj-Si-1`，只需要`Si最小就好了`，不必每次都扫描一遍最小的Si是多少，用一个变量来储存Si的最小值即可。

#include <iostream>
    #include <stdlib.h>
    using namespace std;
    
    int main(){
    
        /*初始化各种需要的变量*/
        int num;
        cin >> num;         //输入被计算的数组的大小
        int A[num];        //初始化被计算的数组A
        for(int i=0;i<num;i++){
            A[i]=rand();
        }
        
        /*计算前n项和*/
        int S[num]={0};    //储存A数组的前n项和。
        S[0] = 0;           //前0项和当然为0
        for(int i =1;i<=num; i++){
            S[i]=S[i-1]+A[i];
        }
    
        /*核心，不断通过更新 最小前n项和 以及 最大（j-i）项和 来获取最终结果*/
        int mins = 0,       //保存当前最小 Si 
        int best = A[1];    //保存当前最大 Sj-Si-1
        for(int i=1; i<=num;i++){
            best = max (best, S[i] -mins) ;
            mins = min (mins, S[i]);
        }
        
        cout<<best<<endl;
        return 0;
    }

--------------------

> ok，列个表格结束此文。  
> |复杂度|N!|2^N| N^3| N^2| N\*logN| N|  
> |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|  
> |单位时间最大规模| 11| 26 |464| 10000| 4.5\*10^6| 1.0\*10^8|  
> |两倍时间最大规模| 11| 27 |584| 14142| 8.6\*10^6| 2.0\*10^8|

转载于:https://www.cnblogs.com/trialley/p/10484156.html

[lizi]: /images/20211223/208c09adfeed472b92a2c92b507fec50.png