A334.时间复杂度测试

此题用以测试时间复杂度
输入N，输出N即可AC。
测试点X对应的N为pow(10,N)
测试模板O(1)

#include<bits/stdc++.h>
using namespace std;
void go(long long n){
	
}
int main(){
	long long n;
	cin>>n;
	go(n);
	cout<<n;	
}

常见复杂度

//O(N)
for(long long i=1;i<=n;i++); 

O(N^2)
for(long long i=1;i<=n;i++){
	for(long long j=1;j<=n;j++);
}
for(long long i=1;i<=n;i++){
	for(long long j=1;j<=i;j++);
}

O(N*sqrt(N))
for(long long i=1;i<=n;i++){
	for(long long j=1;j*j<=n;j++);  //  j<=n/j ,j<=sqrt(n)
}

O(N*log(N))
for(long long i=1;i<=n;i++){
	for(long long j=1;j<=n;j*=2);  
}
for(long long i=1;i<=n;i++){ //调和级数复杂度
	for(long long j=1;j<=n;j+=i);  
}

N

N

结论

$O(N) 10^{8}$

$O(N^2) 10^{4}$

$O(Nsqrt(N)) 10^{5}$

$O(Nlog(N)) 10^{7}$

$可AC$