时空复杂度

时间复杂度用T=O(n) 类似于 y=f(x)

n代表数据数量

O代表时间复杂度函数

时间复杂度指当数据量为n时，基本代码的执行次数

基本代码：通常指循环最内部的代码块

时空复杂度通常用于【估算】算法的时长是否超时

int a[100005];

int n;

cin>>n;

for(int i=0;i<n;i++) cin>>a[i];

for(int i=0;i<n;i++) cout<<a[i]<<" ";

时间复杂度记为T=O(n)

int fb(int n){

   if(n<2) return 1;

   return fb(n-1)+fb(n-2);

}

时间复杂度记为T=O(2^n)

for(int i=0;i<n;i++){

   for(int j=0;j<n-i;j++){

       if(a[j]>a[j+1]) swap(a[j],a[j+1]);

   }

}

时间复杂度记为T=O(n^2)    (n+1)*n/2 -> n^2

int l=0,r=n;

while(l<r){

   int mid=(l+r)/2;

   if(---) l=mid+1;

   else r=mid-1;

}

时间复杂度记为T=O(logn)

int a[12]={31,28,31,30,31,30,31,31,30,31,30,31};

int n;

cin>>n;

cout<<a[n-1];

时间复杂度记为T=O(1)

for(int i=2;i<maxnum;i++){

   if(a[i]==0){

       for(int j=i*i;j<=maxnum;j+=i){

           if(a[i]==0) a[i]=1;

       }

   }

}

素数筛时间复杂度记为O(n) 或O(maxnum)

利用素数筛完成多次的素数判断 O(1) 常数级

T=O(1)>O(logn)>O(n)>O(nlogn)>O(n^2)>O(2^n)>O(3^n)>O(n!)