赞
踩
一,时间复杂度
一个算法需要的运算时间常与问题规模有关,问题规模是一个和输入有关的量n,通常把算法运行需要的时间T表示为n的函数,为T(n)
不同的算法中,n增长时,T增长的快慢很不相同,一个算法所需的执行时间就是该算法中所有语句执行次数之和,当n逐渐增大时,T(n)的极限情况,简称为时间复杂度
二,常用的时间复杂度大小次序
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
数量级越大,该算法效率越低
三,分析算法时间复杂度
- x=0;y=0;
- for(k=1;k<=n;k++)
- x++;
- for(i=1;i<=n;i++)
- for(j=1;j<=n;j++)
- y++;
-
- 分析:
- 其包含两个循环体,第一个循环的时间复杂度为n
- 第二个是双重循环,其时间复杂度为n^2,所以以上程序的时间复杂度是:T(n)=n+n^2
-
- 则其时间复杂度为:T(n)=O(n^2)
- i=1;
- while(i<=n)
- i=2*i;
-
- 分析:
- 第3行执行次数是f(n),则2^f(n)<=n
-
- 所以T(n)=O(log2n)
- void mult(int a[][N],int b[][N],int c[][N])
- {
- for(i=0;i<n;i++)
- for(j=0;j<n;j++)
- {
- c[i][j]=0;
- for(k=0;k<n;k++)
- c[i][j]+=a[i][k]*b[k][j];
- }
- }
-
- 分析:
- 嵌套循环为每层循环次数的乘积,因为该函数三重循环
- 所以时间复杂度为:T(n)=O(n^3)
四,例题
例题一:(洛谷) P2249 查找
分析:
1,一般测试点都会有一个极限数据,所以要分析时间复杂度,确保能过所有测试点。
2,如果用平常的循环访问查找,n个系数,处理m个访问,其时间复杂度是O(nm)=10^6 * 10^5 = 10^11,而测评机1秒只会执行10^9次运算,所以一定会超时,因此要寻找其他算法来解题。
3,查找算法中,根据不同情况有不同解法,我们先接触到的是二分算法,其时间复杂度是O(log2n),所以值得一试。
代码如下:
- #include<bits/stdc++.h>
- using namespace std;
- #define N 1000006
-
- int n,m,a[N],s;
-
- int find(int s){//二分算法本体
- int r=n,l=1;
- while (r>l)
- {
- int mid = (r+l)/2;
- if(a[mid] >= s)r = mid;
- else l = mid+1;
- }
- if(a[l] == s)return l;
- else return -1;
- }
-
- int main(){
- cin>>n>>m;
- for(int i = 1;i <= n;i++){
- cin>>a[i];
- }
- for(int j = 1;j <= m;j++){
- cin>>s;
- cout<<find(s)<<" ";
- }
- return 0;
- }
例题二:(洛谷) P8780 [蓝桥杯 2022 省 B] 刷题统计
分析:
先看问题规模,如果用普通循环来计算,必超时,但是这题又不用查找,所以要想办法,把不必要的计算部分舍掉。
代码如下(简单版):
- #include<iostream>
- using namespace std;
-
- int main(){
- long long a,b,c,i,weeks,left,sum=0;
- cin>>a>>b>>c;
- weeks = c / (a*5+b*2);//需要几个星期
- left = c % (a*5+b*2);//几个星期之后剩的题
-
- for(i =1;i <= 7;i++){//剩下的题会在这个星期之内做完
- if(i>5){
- sum += b;
- if(sum >= left)break;//如果剩下的题能在这次sum中做完,就结束
- }
- else {
- sum += a;
- if(sum >= left)break;
- }
- }
- if(left == 0)cout<<weeks*7<<endl;
- else cout<<weeks*7+i<<endl;
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。