ThinkSSL🔒 一键申购 5分钟快速签发 30天无理由退款 购买更放心 广告
[TOC] ### **算法是什么** 算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有很大的区别。 ### **如何衡量不同算法之间的优劣?** * 时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。 * 空间维度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述。 #### **时间复杂度** 通用的方法就出来了:「**大O符号表示法**」,即 T(n) = O(f(n)) 例子: ``` for(i=1; i<=n; ++i) { j = i; j++; } ``` **算法的渐进时间复杂度**: 在 大O符号表示法中,时间复杂度的公式是: T(n) = O( f(n) ),其中f(n) 表示每行代码执行次数之和,而 O 表示正比例关系。 >假设每行代码的执行时间都是一样的,我们用 1颗粒时间 来表示,那么这个例子的第一行耗时是1个颗粒时间,第三行的执行时间是 n个颗粒时间,第四行的执行时间也是 n个颗粒时间(第二行和第五行是符号,暂时忽略),那么总时间就是 1颗粒时间 + n颗粒时间 + n颗粒时间 ,即 (1+2n)个颗粒时间,即: T(n) = (1+2n)\*颗粒时间,从这个结果可以看出,这个算法的耗时是随着n的变化而变化,因此,我们可以简化的将这个算法的时间复杂度表示为:T(n) = O(n) 为什么可以这么去简化呢,因为大O符号表示法并不是用于来真实代表算法的执行时间的,它是用来表示代码执行时间的增长变化趋势的。 所以上面的例子中,如果n无限大的时候,T(n) = time(1+2n)中的常量1就没有意义了,倍数2也意义不大。因此直接简化为T(n) = O(n) 就可以了。 #### **时间复杂度量级** ##### 常数阶级O(1) 无论代码执行了多少行,只要是没有循环等复杂结构,那这个代码的时间复杂度就都是O(1) ``` int i = 1; int j = 2; ++i; j++; int m = i + j; ``` ##### 线性阶O(n) for循环里面的代码会执行n遍,因此它消耗的时间是随着n的变化而变化的,因此这类代码都可以用O(n)来表示它的时间复杂度。 ``` for(i=1; i<=n; ++i) { j = i; j++; } ``` ##### **对数阶O(logN)** 代码: ``` int i = 1; while(i<n) { i = i * 2; } ``` 在while循环里面,每次都将 i 乘以 2,乘完之后,i 距离 n 就越来越近了。我们试着求解一下,假设循环x次之后,i 就大于 2 了,此时这个循环就退出了,也就是说 2 的 x 次方等于 n,那么 x = log2^n 也就是说当循环 log2^n 次以后,这个代码就结束了。因此这个代码的时间复杂度为:**O(logn)** ##### **线性对数阶O(nlogN)** 线性对数阶O(nlogN) 其实非常容易理解,将时间复杂度为O(logn)的代码循环N遍的话,那么它的时间复杂度就是 n \* O(logN),也就是了O(nlogN)。 就拿上面的代码加一点修改来举例: ``` for(m=1; m<n; m++) { i = 1; while(i<n) { i = i * 2; } } ``` ##### **平方阶O(n²)** 把 O(n) 的代码再嵌套循环一遍,它的时间复杂度就是 O(n²) 了。 ``` for(x=1; i<=n; x++) { for(i=1; i<=n; i++) { j = i; j++; } } ``` ##### **立方阶O(n³)**、**K次方阶O(n^k)** 参考上面的O(n²) 去理解就好了,O(n³)相当于三层n循环 #### **空间复杂度** ##### **空间复杂度 O(1)** 如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1) ``` int i = 1; int j = 2; ++i; j++; int m = i + j; ``` 代码中的 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1) ##### **空间复杂度 O(n)** ``` int[] m = new int[n] for(i=1; i<=n; ++i) { j = i; j++; } ``` 第一行new了一个数组出来,这个数据占用的大小为n,这段代码的2-6行,虽然有循环,但没有再分配新的空间,因此,这段代码的空间复杂度主要看第一行即可,即 S(n) = O(n)