A422. 时间复杂度测试

此题用以测试时间复杂度
输入 $N$，输出 $N$ 即可AC。


测试点 $X$ 对应的 $N$ 为 pow(10,X)
测试模板时间复杂度为 $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}$