理解了时间复杂度的概念后，就可以根据实际的代码进行度量了，以下举例了几个常用的时间复杂度的表示，对于如何度量其最重要的是观察程序中的循环结构，每一个循环结构代表执行循环中的指令n次，而其余指令一般而言一行代码代表执行一次，对于一个程序而言，执行的次数相差较小其实没有什么区别，都是一瞬间执行完毕。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
1. 度量时间复杂度文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
a)O(1) / O(C) C代表常数文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
1 2 3 4 5 | #include<stdio.h>int main(){ printf("Hello World"); //执行一次 return 0; //执行一次} |
对于如上代码，执行了两次，即O(2)=O(1)，我们可以称其时间复杂度为O(1)，或者常数级时间复杂度文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
b)O(n)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
1 2 3 4 5 6 7 8 | #include<stdio.h>int main(){ int n=10000,ans=0; //执行一次 for(int i=0;i<n;i++){ //执行n次 ans+=i; //执行一次 } return 0; //执行一次} |
对于如上代码，我们一共执行了n*1+2次，即O(n*1+2)，由上文我们的公式得到其复杂度为O(n)，或称之为线性阶时间复杂度。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
c)O(n^2)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
1 2 3 4 5 6 7 8 9 10 | #include<stdio.h>int main(){ int n=10000,ans=0; //执行一次 for(int i=0;i<n;i++){ //执行n次 for(int j=0;j<n;j++){ //执行n次 ans+=j; } } return 0; //执行一次} |
对于如上代码，我们一共执行了n*n*1+2次，即O(n*n*1+2)，由上文我们的公式得到其复杂度为O(n^2)，或称之为平方阶时间复杂度，此外还有三层循环结构嵌套组成的O(n^3)级别的时间复杂度，称之为立方阶时间复杂度，随着嵌套的增多，甚至还有O(n!)级，称之为阶层级时间复杂度，但是这种级别复杂度极高，程序运行极其缓慢。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
d)O(logn)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
1 2 3 4 5 6 7 8 | #include<stdio.h>int main(){ int i=1,n=10000; //执行一次 while(i<=n){ //执行logn次 i*=2; } return 0; //执行一次} |
对于如下代码，与上文的线性增长不同，其i的增长是倍增的形式，也就是说i会随着运行次数的增加变大的趋势变更大，这样会比那些简单的用加法上涨的变量更快到达循环结构的边界，这样的代码时间复杂度一般为log级别，对于本样例，有O(logn+2)=O(logn)，称之为对数阶时间复杂度文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
e)O(n*logn)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
1 2 3 4 5 6 7 8 9 10 11 | #include<stdio.h>int main(){ int n=10000,ans=0; //执行一次 for(int i=0;i<n;i++){ //执行n次 int j=0; //执行1次 while(j<=n){ //执行log(n)次 j*=2; } } return 0; //执行一次} |
对于上文的对数级别的时间复杂度，一样可以实用别的循环进行嵌套，比如本样例O(n*(logn+1)+2)=O(n*logn)级别文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
除此之外还有很多种时间复杂度的组合，比如说O(2^n)这样的指数阶时间复杂度，有时甚至需要引入多个变量乃进行表示，不过最核心的还是要观察循环结构的处理。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
2.各个复杂度的比较文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
如图，我们以x轴为n的规模，y轴为整体的计算次数，可以发现其明显的计算区别，立方级别似乎很小的数就变得需要很多得计算了，而相对得logn级别得复杂度似乎无论怎么增加n，其涨幅都不是很明显。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
然而事实上，计算机的计算次数何止60次啊，计算机真实的计算速度是论千论万论亿级别的计算，所以我们的n会变得非常之大，让我们把坐标进行变化，以10000为界进行理解。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
可以见到，平方以及立方级别的复杂度几乎已经是平贴着y轴的一条直线了，而O(n*log(n))与O(n)还保持着一定的速率进行增长，log(n)又是另一个极端，它变成了一个几乎贴着x轴的直线，这样算法的效率就轻易看得出了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
综上可以直观的得出：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html
在设计程序的时候一定要注意，高计算需求的地方一定不要使用太高的时间复杂度的计算方式.文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25032.html