本来是想出两个系列，一个算法题解，一个算法思想，但是讲思想必须用到题目，题目里也必然蕴含思想，不如两者合并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问题那些信仰一样的瞎**扯的东西?
空间复杂度
- 指程序占用的空间大小，一般来说，对同一个需求，时间复杂度越大，空间复杂度越小，即时间空间是互补的。但是一般编程时对时间复杂度最关心。
如何估计时间复杂度
- 默认估算最坏情况下的时间复杂度
- 加法：多个循环或分支结构之间采用加法
- 乘法：循环嵌套使用乘法
- 分支结构：多分支中选择时间复杂度最大的分支
举个例子
题目文本
给出一个长度为n的数列A1，A2，…，An，求最大连续和。换句话说，要求找到1≤i≤j≤n，使得Ai + Ai+1 + … + Aj尽量大。
这里有多种不同复杂度的方法
暴力穷举O(n^3)
两个循环确定被计算的子序列的两端，一个循环用来计算子序列的和，不断比较和的大小。懒得写代码了。
数组辅助O(n^2)
将计算的和放到数组中，可以有效避免重复计算
#include#include using namespace std;int main(){ /*初始化各种需要的变量*/ int num; cin >> num; //输入被计算的数组的大小 int A[num]; //初始化被计算的数组A for(int i=0;i
二分法O(n*logn)
一般用二分法的算法复杂度都是O(n*logn)
待补充，反正只需要知道二分法的复杂度是O(n*logn)就行了?
更nb的数组辅助O(n^2)
继承方法2的思想，要想获得最大连续和
Sj-Si-1，只需要Si最小就好了，不必每次都扫描一遍最小的Si是多少，用一个变量来储存Si的最小值即可。
#include#include using namespace std;int main(){ /*初始化各种需要的变量*/ int num; cin >> num; //输入被计算的数组的大小 int A[num]; //初始化被计算的数组A for(int i=0;i
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|