学习总结：复杂度

在程序设计时，我们必须要考虑程序的运行效率，那么就要求我们在写程序时，尽可能的优化算法。
在程序设计中，描述程序运行效率的有空间复杂度和时间复杂度。
空间复杂度S(n)：根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。如果一个程序在运行时需要开辟很多空间，那么它很有可能崩溃。
例如：
如果让我们输出0到n的整数，我们可以利用for循环或者递归；
循环：

#include<iostream>
using namespace std;
int main(){
	int n;
	cin>>n;
	for(int i=0;i<=n;i++)
		cout<<i<<endl; 
	return 0;
}

递归：

#include<iostream>
using namespace std;
void print(int x){
	if(x) print(x-1);
	cout<<x<<endl;
	
}
int main(){
	int n;
	cin>>n;
	print(n);
	return 0;
}

当n=10的时候的运行结果时两个程序都正常的输出了
但是当n=100000的时候
循环输出虽然等了一段时间，但是可以正常输出
学习总结：复杂度
递归的代码的结果是崩溃

这就是因为递归的空间复杂度过高导致的。
时间复杂度O(n)：根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。
例如计算这样一个多项式的值：
a0+a1*x^1 + a2 x ^2+…+anx ^n
如果直接按这个多项式写程序，那么这就是猪的行为。
因为有比这更好的办法。
秦九韶将这个多项式进行了化简：
a0+x(a1+x(…(an+1+x(an))…))
两个程序分别为：

double f(int n,double a[],double x)
{
	int i;
	double p=a[0];
	for(i=1;i<=n;i++)
		p+=(a[i]*pow(x,i));
	return p;
}

double f(int n,double a[],double x)
{
	int i;
	double p=a[n];
	for(i=n;i>0;i--)
		p=a[i-1]+x*p;
	return p;
}

很明显的可以看出
第一种进行了(n^2+n)/2次乘法运算
第二种只进行了n次乘法运算
第一种的时间复杂度是 c*n^2
第二种的时间复杂度是 n
所以当n很大时第二种要比第一种运算快的多。

学习总结：复杂度

相关推荐