算法的复杂度
大o复杂度表示法
公式:
t(n)表示代码执行的时间; n表示数据规模的大小; f(n) 表示每行代码执行的次数总和。因为这是一个公式， 所以用f(n)来表示。公式中的o,表示代码的执行时间t(n)与f(n)表达式成正比。
所以，第一个例子中的t(n) = o(2n 2)，第二个例子中的t(m) = 0(2n2 2n 3)。这就是大o时间复杂度表示法。大o时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度(asymptotic time complexity)，简称时间复杂度。
当n很大时，你可以把它想象成10000、100000。 而公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大o表示法表示刚讲的那两段代码的时间复杂度,就可以记为: t(n) = o(n); t(n)= 0(n2)。
复杂度分析法则
1）单段代码看高频：比如循环。
2）多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
3）嵌套代码求乘积：比如递归、多重循环等
4）多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。
时间复杂度分析
- 只关注循环执行次数最多的一段代码
- 加法法则：总复杂度等于量级最大的那段代码的复杂度
- 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
几种常见时间复杂度实例分析
多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括，
o(1)（常数阶）、o(logn)（对数阶）、o(n)（线性阶）、o(nlogn)（线性对数阶）、o(n^2)（平方阶）、o(n^3)（立方阶）
非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括，
o(2^n)（指数阶）、o(n!)（阶乘阶）
- o(1) :
常量级时间复杂度,只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 o(1)。
- o(logn)、o(nlogn)
i=1;
while(i<=n) {
i = i*2;
}x=log2n，所以，这段代码的时间复杂度就是 o(log2n)
- o(m n)、o(m*n)
int cal(int m, int n) {
int sum_1=0;
int i=1;
for(;i
从代码中可以看出，m和n是表示两个数据规模。我们无法事先评估m和n谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复 杂度就是0(m n)。
针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为: t1(m) t2(m) = o(f(m) g(n))。但是乘法法则继续有效: t1(m)*t2(n) = o(f(m) * f(n))。
空间复杂度分析
表示算法的存储空间与数据规模之间的增长关系。
void print(int n) {
inti=0;
int[] a = new int[n];
for (i; i =0;--i){
print out a[i]
}
}
跟时间复杂度分析一样，我们可以看到，第2行代码中，我们申请了一个空间存储变量i,但是它是常最阶的，跟数据规模n没有关系，所以我们可以忽略。第3行申请了一个大小为n的int类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是o(n)。
我们常见的空间复杂度就是o(1)、o(n)、 o(n2), 像o(logn)、o(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。所以，对于空间复杂度，掌握刚我说的这些内容已经足够了。
复杂度增长趋势图:
最好情况时间复杂度、最坏时间复杂度、平均情況时间复杂度、均摊时间复杂度。
一、复杂度分析的4个概念
1.最坏情况时间复杂度：代码在最坏情况下执行的时间复杂度。
2.最好情况时间复杂度：代码在最理想情况下执行的时间复杂度。
3.平均时间复杂度：代码在所有情况下执行的次数的加权平均值。
4.均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。
二、为什么要引入这4个概念？
1.同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度，所以引入这4个概念。
2.代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下，是不需要区别分析它们的。
三、如何分析平均、均摊时间复杂度？
1.平均时间复杂度
代码在不同情况下复杂度出现量级差别，则用代码所有可能情况下执行次数的加权平均值表示。
2.均摊时间复杂度
两个条件满足时使用：
1）代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度；
2）低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。