算法时间复杂度O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)、O(n^3)、O(2^n)、O(n阶乘)
例题才是最好的老师？算法时间复杂度O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)、O(n^3)、O(2^n)、O(n阶乘)
目录
注：此博客以基础例题为例，掌握基本的时间复杂度计算。（在做题中学习）
基础常识：
保最大，去系数
删掉小项，只保留对时间复杂度影响最大的项------->再去掉系数
时间复杂度所耗费时间从小到大依次是：
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)
常见的八种时间复杂度类型：
（1）O(1)
常量阶，运行时间为常量
int a=1 //执行1次
print(a) //执行1次
T（N）=1+1=O（1）
（2）O(logn)
对数阶，二分搜索算法等
i=n； //执行1次
while（i>0) i=i/2; //设执行了k次
以8为例：8*1/2=4----->4*1/2=2----->2*1/2=1
(1是最小元素，已经不可再分)
即8*（1/2）^3=1
综上：
有n个元素，即i=n,设执行了k次
===》 n*(1/2)^k=1
==》 n=2^k
==》 k=log(2)n
所以时间复杂度为O(logn)
（3）O(n)
线性阶，如n个数内找最大值
int i , n = 1000, sum = 0; //执行1次
for( i=0; i < n; i++ ) //执行n+1次
{
sum = sum + i; //执行n次
}
T（N）=1+（n+1）+n------>O（n）
（保最大，去系数）
（4）O(nlogn)
对数阶，如快速排序算法
for（int i=1;i<=n;i++） // 执行n次
{
for(int j=1;j<=n;j+=i) //
{ }
}
通过第二个式子对i和n之间的关系进行分析：
（1）当i=1时，执行n次；
（2）当i=2时，执行n/2次；
.............
（4）当i=n-1时，执行n/n-1次；
（5）当i=n时，执行n/n次；
第二个式子：
执行n(1 +1/2+1/3 +1/4 + 1/5+ 1/6+1/7+1/8 +...1/n)次
（查阅资料知）
这是一个调和级数
1+1/2+1/3+1/4+...+1/n= ln(n+1)+r(r为常量)
n(1 +1/2+1/3 +1/4 + 1/5+ 1/6+1/7+1/8 +...1/n)
=n(ln(n+1) + r)
=nln(n+1)+rn
所以时间复杂度为O（nlogn）
（5）O(n^2)
平方阶，如选择排序，冒泡排序
int i, j, n = 1000; //执行1次
for( i=0; i < n; i++ ) //执行n+1次
{
for( j=0; j < n; j++ ) //执行n(n+1)次
{
print(j); //执行n(n+1)次
}
}
T（N）=1+（n+1）+2n（n+1）------>O（n^2）
（保最大，去系数）
（6）O(n^3)
立方阶，如两个n阶矩阵的乘法运算
int a, b,c,long sum = 0 //执行1次
for (int x = 0; x < a; x++) //执行n+1次
for (int y = 0; y < b; y++) //执行n(n+1)次
for(int z=0;z<c;z++) //执行（n+1）n^2次sum=a*b*c //执行n^3次
T(n)=1+(n+1)+n(n+1)+n^2(n+1)+n^3
=O(n^3)
（7）O(2^n)
指数阶，如n个元素集合的所有子集的算法
int i = 1, n = 1000; //1
while( i < n ) //设执行x次
{
i = i * 2;
}
设执行x次i=n，即2^x=n--->x=log(2)n
T(N)=O(log(2)n)-------->(原来这个不是)
for(int i=0;i<pow(2,n);i++)
{
……
}
for(int i=0;i<pow(n,n);i++)
{
……
}
多项式最大阶：
f(n)=a1*n^m+a2*n^(m-1)+.an-1*n+an
时间复杂度T(f(n))=O(n^m)
时间步法
一个函数g(n),一个自然数n0,使f(n)<=n0*g(n)
有T(f(n))=O(g(n)),简称为T(n)=O(g(n))
(1)f(n)=n+2log2n<=n+2n=3n=3*g(n)==>T(n)=O(n)
(2)6n^2-12n+1<=6n^2-n^2(n>=12)=7n^2=7*g(n)==>T(n)=O(n^2)
(3)n(n+1)(n+2)/6<=n(n+1)(n+2)=n(n^2+3^n+2)=n^3+3n^2+2n<=n^3+4n^2(n>=n0=2时）<=2n^3(n>=n0=4)=2*g(n)===>T(n)=O(n^3)
(4)2^(n+1)+100n<=2*2^n+n*2^7<=3*2^n=3*g(n)==>T(n)=O(2^n)
（8）O(n!)
阶乘阶，如n个元素全部排列的算法
int fac(int n)
{ if n == 1 or n == 0
{ return 1;}
else
{ return n*fac(n-1); }
}
T(n)=
O(1),n≤1
T(n−1)+O(1),n>1
T(n)=T(n−1)+O(1)
=T(n−2)+2O(1)
=...=T(1)+(n−1)O(1)
=O(1)+(n−1)O(1)=O(n)
- 点赞
- 收藏
- 关注作者
评论（0）