时间复杂度概念

· · 算法·理论

概念

==时间复杂度是程序中通用的程序运算时间表示方式==（又称大O表示法）。主要形式为O(表达式)。如O(n)。参数有n。时间复杂度是个抽象的概念。

常见的时间复杂度

常数阶

表示方式为 O(1) ，是最低的复杂度 例子：输出文本等 代码

#include <iostream>
using namespace std;
int main()
{
    cout<<"Hello, World!"<<endl;        // 此处时间复杂度为O(1)
    return 0;
}

注意：表示时要将所有系数转化为1或省略

例如：

#include<bits/stdc++.h>
using namespace std;
int main(){
    cout<<"Hello, ";
    cout<<"World!"<<endl;       // 此处时间复杂度依然为O(1)，O(2)经过化简系数后为O(1)
    return 0;
}

对数阶

表示方式为 O(\log_2n) 例子：对分查找等

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    int a[n];for(int i=0;i<n;i++)cin>>a[i];
    int key;cin>>key;
    int left=0,right=n-1;
    while(left<=right){         // 此处时间复杂度为O(log_2 n)
        int mid=left+(right-left)/2;
        int(a[mid]==key){
            cout<<mid<<endl;
            return 0;
        }else if(a[mid]<key)left=mid+1;
        else right=mid-1;
    }
    cout<<-1<<endl;
    return 0;

线性阶

表示方式为 O(n) 例子：输出数组等

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    int a[n];for(int i=0;i<n;i++)cin>>a[i];         // 此处也为O(n)
    for(int i=0;i<n;i++)cout<<a[i]<<" ";            // 此处为O(n)
    return 0;
}

线性对数阶

表示方式为 O(n\log_2n) 例子：归并排序

#include<bits/stdc++.h>
using namespace std;
void mergesort(vector<int>& a){         // 函数中的时间复杂度为O(n log_2 n)
    if(a.size()>1){
        int mid=a.size()/2
        vector<int> left,right;
        for(int i=0;i<=mid;i++)left[i]=a[i];
        for(int i=0;i<=mid;i++)right[i]=a[mid+i];
        mergesort(left);
        mergesort(right);
        int i=0,j=0,k=0;
        while(i<left.size()&&j<right.size()){
            if(left[i]<right[j])a[k++]=left[i++];
            else a[k++]=right[j++];
        }while(i<left.size())a[k++]=left[i++];
        while(j<right.size())a[k++]=right[j++];
    }
}
int main(){
    int n;cin>>n;
    vector<int> a(n);for(int i=0;i<n;i++)cin>>a[i];
    mergesort(a);
    for(int i=0;i<a.size();i++)cout<<a[i]<<" ";
    return 0;
}

二次阶

表示方式为 O(n^2) 例子：读入二维数组等

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;cin>>n>>m;
    int a[n][m];
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>a[i][j];           // 此处为O(n^2)
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)cout<<a[i][j]<<" ";         // 此处也为O(n^2)
    return 0;
}

三次阶

表示方式为 O(n^3) 例子：读入三维数组等

#include<bits/stdc++.h>
using namespace std;
int main(){
    int m,n,o;cin>>m>>n>>o;
    int a[m][n][o];
    for(int i=0;i<m;i++)for(int j=0;j<n;j++)for(int k=0;k<o;k++)cin>>a[i][j][k];        // 此处为O(n^3)
    for(int i=0;i<m;i++)for(int j=0;j<n;j++)for(int k=0;k<o;k++)cout<<a[i][j][k]<<" ";      // 此处也为O(n^3)
    return 0;
}

指数阶

表示方式为 O(2^n) 例子：斐波那契数列等

#include<bits/stdc++.h>
using namespace std;
int fibonacci(int n){       // 函数体内为O(2^n)
    if(n<=1)return n;
    return fibonacci(n-1)+fibonacci(n-2);
}
int main(){
    int n;cin>>n;
    cout<<fibonacci(n)<<endl;
    return 0;
}

感谢您的观看！！