概念

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

常见的时间复杂度

常数阶

表示方式为

O(1)

，是最低的复杂度例子：输出文本等代码

CPP

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

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

例如：

CPP

#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)

例子：对分查找等

CPP

#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)

例子：输出数组等

CPP

#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)

例子：归并排序

CPP

#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)

例子：读入二维数组等

CPP

#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)

例子：读入三维数组等

CPP

#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)

例子：斐波那契数列等

CPP

#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;
}

感谢您的观看！！

时间复杂度概念

文章操作

概念

常见的时间复杂度

常数阶

对数阶

线性阶

线性对数阶

二次阶

三次阶

指数阶

相关推荐

评论

时间复杂度概念