算法学习 (第一部分)

第一部分 性能分析

1.时间复杂度

问题计算所需时间同问题规模n的关系,采用大O表示法.

常数阶O(1)-> 对数阶O(log2n)-> 线性阶O(n) ->线性对数阶O(nlog2n)->平方阶O(n2)->立方阶O(n3),...，-> k次方阶O(nk)->指数阶O(2n)。

随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

(1).举个例子

求:x的n次方

int function1(int x,int n){
	int result = 1;
	for(int i = 0 ;i <ｎ；ｉ＋＋）
	｛
 		 result *= x;
	 }
	return result;
}

int function2(int x,int n){
	if(n == 0) return 1;
	return function2(x,n-1);
}

int function3(int x,int n){
	if(n == 0) return 1;
	if(n%2 == 1) return function3(x,n/2)*function3(x,n/2)*x;
	return function3(x,n/2)*function3(x,n/2);
}

int function4(int x,int n){
	if(n == 0) return 1;
	int t = function4(x,n/2)
	if(n%2==1) return t*t*x;
	return t*t;
}

可以看到不同的方法可以使软件的时间空间复杂度截然不同

2.c++的内存管理

(1)理解c++的内存管理

(2)理解为何需要内存对齐?

• 不是所有的硬件平台都允许访问任意内存地址的数据,某些平台只能在一些地址获取特定类型的数据,否则抛出硬件异常,为了同一程序在不同平台运行,需要内存对齐
• 对齐内存后虽然会损失一部分空间,可是能极大提升cpu访问内存的速率(具体原因理解cpu是按块读取内存的,对齐使访问更直接)

3.空间复杂度

同理 所需空间同问题规模的关系也可以使用大o表示法,注意空间复杂度为O(1)也成为就地执行.一般的我们使用空间来换取时间.

(1) 举个例子

int feibo1(int n)
{
//完全的递归
if(n<=0) return 0;
if(n==1||n==2) return 1;
if(n==3) return 2;
else return feibo1(n-1)+feibo1(n-2);
}

int feibo2(int first,int second,int n)
{
//精简解法 应当理解
if(n<=0) return 0;
if(n<3) return 1;
if(n ==3) return first+second;
else return feibo2(second,first+second,n-1);
}

int feibo3(int n)
{
//使用数组存储
if(n<=0) return 0;
if(n==1||n==2) return 1;
vector num{1,1};
num.reserve(n+2);
vector::iterator it;
for(int i = 0; i < n-2 ;i++)
{
num.push_back(num.at(i)+num.at(i+1));
}
return num.back();
}