每一题都有一个时间限制，一般是1秒，也就是大约 1 \times 10^7 次。
时间复杂度有这样几种：
O(1) ：无循环算法类，数据限制 无
比如
#include<iostream>
using namespace std;
int main(){
cout<<"Hello,World!";
return 0;
}
O(log_2(n)) ：二分算法等，数据限制 n \leq 2^{1 \times 10^7}
比如
#include<iostream>
using namespace std;
int n,a[15],t,l,r,mid;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
cin>>t;
l=1;
r=n;
while(l<=r){
mid=l+(r-l)/2;
if(a[mid]<t){
l=mid+1;
}
else{
r=mid-1;
}
}
cout<<l;
return 0;
}
O(n) ：单层for循环算法等，数据限制 n \leq 1 \times 10^7
比如
#include<iostream>
using namespace std;
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cout<<i<<" ";
}
return 0;
}
O(nlog_2(n)) ：快排等，数据限制 n \leq 1.3 \times 10^6
比如
#include<iostream>
#include<algorithm>
using namespace std;
int n,a[15];
int findpos(int l,int h){
int p=a[h];
int ii=l-1;
for(int i=l;i<h;i++){
if(a[i]<=p){
ii++;
swap(a[ii],a[i]);
}
}
swap(a[ii+1],a[h]);
return ii+1;
}
void qs(int l,int h){
if(l<h){
int pos=findpos(l,h);
qs(l,pos-1);
qs(pos+1,h);
}
}
int main() {
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
qs(0,n);
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
return 0;
}
O(n^2) ：双层for循环算法等，数据限制 n \leq 3000
比如
#include<iostream>
using namespace std;
int n;
int main() {
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%5d",(i-1)*n+j);
}
cout<<"\n";
}
return 0;
}
O(2^n) ：某些递归算法等，数据限制 n \leq 23
比如
#include<iostream>
using namespace std;
int n;
int f(int n){
if(n==0){
return 1;
}
return f(n-1)+f(n-1);
}
int main() {
cin>>n;
cout<<f(n);
return 0;
}
O(n!) ：常见递归阶乘算法，数据限制 n \leq 10
比如
#include<iostream>
using namespace std;
int n;
int f(int n){
if(n==0||n==1){
return 1;
}
return n*f(n-1);
}
int main() {
cin>>n;
cout<<f(n);
return 0;
}
因此有
O(1) \lt O(log_2(n)) \lt O(n) \lt O(nlog_2(n)) \lt O(n^2) \lt O(2^n) \lt O(n!)
所以大家做题的时候一定要深思熟虑时间复杂度哦！
