算法是由若干条指令所组成的的有穷序列,其中每一条指令表示计算机的一个或多个操作。
一个好的算法首先要具备正确性、可读性和健壮性。在具备这三个条件后,就应该考虑算法的效率问题。即算法的时间效率和空间效率两方面。
时间复杂度
一个算法所需要的运算时间通常与解决问题的规模大小有关。问题规模就是一个和输入有关的量,用n来表示问
题的规模的量,通常把算法运行的时间T表示为n的函数,记作T(n)。不同的算法随着n的变化运算时间也不相同。
当n逐渐增大时T(n)的极限情况,一般称为时间复杂度。
当我们讨论一个程序运行时间时,注重的不是T(n)的具体值,而是它的增长率。T(n)的增长率与算法中数据的
输入规模有关,而数据的输入规模往往用法中的某个变量函数来表示通常我们用f(n)。随着数据输入的增大,
f(n)的增长率与T(n)的增长率接近。因此T(n)和发f(n)在数量级上是一致的记作:
T(n) = O(f(n))
计算时间复杂度
1.忽略常数项。 ( 例1:n10 +3 ===> n10)
2.忽略系数。( 例2:3n10 ===> 3n10 )
3.只保留最高项。 ( 例3:n10 + n9 ===> n10)
常见的时间复杂度的大小顺序:
从小到大依次是:O(1)<O(log2n)<O(n)< O(nlog2n)<O(n2)<O ( n^3 ^) <O(2n)
例题1:P8780 [蓝桥杯 2022 省 B] 刷题统计
理论上无法得满分
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
long long a,b,n,x= 0,day=1,ans = 0;
cin>>a>>b>>n;
while(x<n){
if(day == 6 || day == 7) {
x += b;
ans++;
}else{
x+= a;
ans ++;
}if(day >7){
day = 1;
}
day++;
}
cout<<ans;
return 0;
}
分析:
根据要求:
对于100%的数据 要求在1-1018 ,我们考虑最坏的情况:a和b均为1时且 n=1018;在最坏的情况下无法满足对于100%的数据 要求在1-1018 。但是上面的解法依旧能AC,这个题的测试点数据均落在来了1-106。正常来说上面的解法无法取得100分;
正确的写法:
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
long long a,b,n,x,num,ans;
cin>>a>>b>>n;
// 一个星期的做题量
x = 5*a+b*2;
if(n%x == 0){
ans = n/x*7;
}else{
//做了n/x个学期*7=(n/x)星期一个做了多少题
ans = n/x*7;
// 剩余的题量
n = n -n/x*x;
for(int i=1;i<=7;i++){
if(i == 6||i == 7){
n-=b;
}else{
n-=a;
}
if(n<=0){
ans+=i;
break;
}
}
}
cout<<ans;
return 0;
}
例题2:P2249 【深基13.例1】查找
如果直接用暴力for循环来做毋庸置疑一定会超时,根据题目所说:输入 n个不超过 109
的单调不减的非负整数。说明在此我们可以使用二分查找。
如果使用for循环,当 n = 109 时 时间复杂度为 :O(n) = 109;总体上会超时;
但是二分查找的时间复杂度为:O(log2n) 带入 n = 109 得 log2109 < 109
空间复杂度
覃神说:绝大多数情况下不会卡,没啥用。
所以这里可以偷懒不写了!!!