算法的入门

I learn some program algorithm this days

一道题

写一个算法，求下面序列之和：

​ -1，1，-1，1，…，（-1)^n

解法1；

sum = 0 ;
for(i=1; i<=n; i++)
​	sum=sum+pow(-1,n);

解法2；

if（n%2==0）
​	sum=0;
else
​	sum=-1;

解法一、解法二都是算法

好的算法标准是：

1. 正确性
2. 易读性
3. 健壮性
4. 高效性
5. 低存储性

如何保证代码高效？

时间复杂度 (Time Complexity)

时间复杂度：一般算法基本运算执行次数作为时间复杂度的量度标准。

sum=0；      				 //运行1次
total=0；					//运行1次
for(i=1;i<=n;i++) {  		  //运行n+1次，最后判断条件不成立，结束
​	sum=sum+i;				 //运行n次
​	for(j=1;j<=n;j++)		 //运行n*(n+1)次
​		total=total+i*j;	 //运行n*n次
}

算法语句加起来，即1+1+n+1+n+n(n+1)+ n*n，用一个函数表达：

\[T(n)=2n^2+3n+3\]

用极限表示： \(lim(n->无穷) T(n)/f(n)= c (c≠0)\) 想想T(n)图像，一元二次函数图：

是不是有T(n)和c*f(n)之间有个关系呢？

我们比较他们的“相对增长率”，我的理解是“斜率”

O(f(n))来表示时间复杂度渐进上界，通常用这种表示法衡量算法时间复杂度。

再来一个

i=1;          	//运行1次
while(i<=n) {	//运行x次
	i=i*2;	    //运行x次
}

i值：2, 2^2, 2^3, …, 2^x

当i=n时，即2^x=n结束，x=log2(n)，运算次数为1+2log2(n)，时间复杂度渐进上界为O(f(n))=O(log2(n))。

####

时间复杂度在数组的应用

像查找数组位置这些代码是不能直接计算运算次数的。执行次数依赖于x在数组中的位置。有些算法可以用最好情况，最坏情况和平均情况分别求算法复杂度。最坏情况对决策有关键作用。

空间复杂度 (Space Complexity)

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度

算法得存储量包括：

　　1.程序本身所占空间。

　　2.输入数据所占空间。

　　3.辅助变量所占空间。

swap(int x, int y){
	int temp;      //辅助变量
	temp=x;
	x=y;
	y=temp;
}

空间复杂度为O(1)

递归算法中，每一次递推需要一个栈stack空间，属于辅助变量空间。

阶乘问题

 int fac(int n) {
        if (n == 1 || n==0) {
            return 1;				//运行1次
        } else {//递归函数
            return n*fac(n-1);      //运行T(n-1)次
        }
    }

计算机处理阶乘问题使用“栈”的数据结构。规则是“后进先出（LIFO）”

比喻

叠盘子，连续向上放五个盘子（进栈），又依次拿走五个盘子（出栈）

时间复杂度是 \(T(n)=n\)

斐波那契数列算法优化

fib(int n){
	if (n <= 2)
   		return 1;					//运行1次
	else
		return fib(n-1) + fib(n-2);   //运行T(n-1)+T(n-2)次
}

以下优化方法，时间复杂度为O(n)，空间复杂度O(n)。

fib(int n){
	if(n<1)
		return -1;
	int *a = new int [n+1];
	a[1]=1;
	a[2]=2;
	for (int i=3; i<=n; i++)
		a[i]=a[i-1]+a[i-2];			//运行n次
	return a[n];
}

以下优化方法，时间复杂度O(2)，空间复杂度为O(1)

fib(int n){
	if(n<1)
		return -1;
	if(n==1||n==2)
		return 1;
	int *a = new int [n+1];
	s1=1;
	s2=2;
	for (int i=3; i<=n; i++)
		s2=s1+s2;			//运行1次
		s1=s2-s1;			//运行1次
	return s2;
}

对数阶：

　　　　实质上，斐波那契数列时间复杂度还可以进一步降低到对数阶O(logn)。

　　　　我们每次递归都将a+b的值赋给a,把a的值赋给b，通过观察可以发现,从1和

　　　　0开始将规则反复应用n次，将产生一对数fib(n)和fib(n+1),

　　　　现在将这种规则看成a = bq + aq + a*pb = bp + aq,其中p=0,q=1。把这种变

　　　　换称为T变换,Tpq 变换有个特性是 ：

　　　　Tpq 的二次方等于Tp’q’, p’ = pp + qq’q’ = 2pq + q*q。

　　　　即：a = (bp+aq)p+(bq+aq+ap)q+(bq+aq+ap)p

　　　　　　 = b(2pq+q^2)+a(p^2+2pq+2q^2)

　　　　　　b = (bp+aq)p+(bq+aq+ap)q = b(p^2+q^2)+a(q^2+2pq) 　　　　此处p=0，q=1

int fib_iter(int a, int b, int count)
{
    if(count == 0)
        return b;
    return fib_iter(a+b, a, count-1);
}
int fib(int n)
{
    return fib_iter(1, 0, n);
}

增量

我们在写算法的时候应该尽量避开相对增长率比较大的情况。

复杂程度如下

​ O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(n!)<O(n^n)

注意

1. 递归算法的空间复杂度要计算递归使用的栈空间