衡量算法的性能-时空复杂度分析

算法

即存在输入输出,由有限步骤结束的程序.

因此,显而易见,算法并不是指一个单一的标准答案,而是一切能够完成要求的程序都可以称之为算法.但是算法之间根据性能的不同存在差异,评判这个差异的指标就是本篇分享的重点.

评判算法优劣的指标

1.时间复杂度

时间复杂度用O()表示,它的实质是算法的计算次数
这里先列举几个小例子
第一个例子

int n,ans=0;
cin>>n;
for(int i=0;i<n;i++){
	ans++;
}
ans++;
ans++;
ans++;
cout<<ans;

这段程序比较好理解,在这里,for循环中进行了n次运算,而之后对ans又进行了3次运算,在这里我们的有效计算次数为n+3.
但是这里需要注意时间复杂度并不是n+3,因为我们在实际操作时,n是会取到无穷大的,在这里n就是无穷,对于无穷来说,3就可以忽略不计,因此这段程序的时间复杂度为O(n).

再看一下第二个例子

int n,ans=0;
cin>>n;
for(int i=0;i<n;i+=2){
	ans++;
}
cout<<ans;

这次不过多解释,有效计算次数为n/2,但因为n是趋于无穷的,所以时间复杂度仍然为O(n).

第三个例子

int n,ans=0;
cin>>n;
for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
		ans++;
	}
}
for(int i=1;i<=n;i++){
	ans++;
}
cout<<ans;

这次的代码有两个循环,第二个是n,第一个则是作为一个嵌套循环,比较容易得出经过了n*n次循环
这次的有效计算次数为n²+n,由于n趋向无穷,对n²来说,n可以忽略不计,所以这次的时间复杂度为O(n²).

最后一个例子

int arr[101];
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>arr[i];
for(int i=n-1;i>0;i++){
	for(int j=0;j<i;j++){
		if(arr[j]>arr[j+1]){
			swap(arr[j],arr[j+1]);
		}
	}
}

这是一个冒泡排序算法,这次的有效计算次数为1+2+3+...+n-1,由等差数列的求和公式知道为(n²+n)/2.经过前面的例子,想必都知道了时间复杂度就是不带系数最高次项,这里就是O(n²)

经过上面的例子大家应该对算法的时间复杂度有了比较清晰的认识,这里我再补充几点
1.有限计算次数即没有n加入的程序,规定时间复杂度为O(1).
2.常见的时间复杂度有:O(1),O(logn),O(n),O(n²),O(n³).

2.空间复杂度

事实上在实际情况下,空间复杂度没有时间复杂度受重视,在实际学习中,大多数情况下是超过了运行时间,而不是超过规定内存.但它同样需要我们了解.
时空复杂度也用O()表示,它的实质是额外产生的空间.

int arr[101];
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>arr[i];
int *arr=new int[n];
for(int i=n-1;i>0;i++){
	for(int j=0;j<i;j++){
		if(arr[j]>arr[j+1]){
			swap(arr[j],arr[j+1]);
		}
	}
}
delete[]arr;

这里需要关注的是空间复杂度是额外产生的空间,因此初始的n个不计入空间复杂度,而之后的new出来的内存是空间复杂度,即为n,它的计算方法和时间复杂度一样,取不带系数的最高次项.
补充几点:
1.时间和空间往往是相对的.
2.常见的空间复杂度:O(1),O(n),O(logn*n)

3.稳定性

这里简单提一下,不过多赘述,后续会专门开一个新坑讲解一下.