求助,关于时间复杂度
查看原帖
求助,关于时间复杂度
556362
Unnamed114514楼主2022/9/25 23:54

RT,这是我写的一个倍增的代码:

#include<bits/stdc++.h>
using namespace std;
int s,t,c,a,b;
int main(){
	cin>>a>>b;
	c=a+b;
	if(c>=0){
		while(c){
			t=1;
			while(t*2<=c)
				t*=2;
				s+=t,c-=t;
			}
		cout<<s<<endl;
	} else{
		while(c){
			t=-1;
			while(t*2>=c)
				t*=2;
			s+=t,c-=t;
		}
		cout<<s<<endl;
	}
	return 0;
}

现在只有 TLE 90,T 的那个点是极限数据,但是我感觉这个复杂度应该是没有问题的,是一个 O(log2(a+b))O(\log^2(a+b)) 的复杂度。是复杂度算错了吗?

2022/9/25 23:54
加载中...