14天阅读挑战赛 *努力是为了不平庸~ 每个学习算法的都需要一把打开算法的钥匙,就如陶渊明的《桃花源记》中 ”初极狭才通人,复行数十步,豁然开朗“。
写一个算法,求一下序列之和:
当你看到这个题目的时候,你会怎么想?for循环?while循环? 先看for循环的代码
int sum1(int n){
int sum=0;
for(int i=1;i<=n;i++)
sum+=pow(-1,i);//表示(-1)^i
return sum;
}
上面这段代码,确实可以实现求和运算,但是为什么不这样算呢?
再看另一种写法:
int sum2(int n){
int sum=0;
if(n%2==0)
sum=0;
else
sum=-1;
return sum;
}
看到这段代码后,是不是恍然大悟,原来还可以这样啊,这不就是数学家高斯使用的算法吗?
一共50对数,每对数的和均为101,因此总和为:
(1+100)* 50 = 5050
1787年,10岁的高斯用了很短的时间就算出了结果,而其他小孩子用了半天。 可以看出,使用for循环的话,需要循环n次,每次循环内还要pow运算,然后再相加运算。如果n = 10000,那么就算运算 10000次这样的过程。而通过我们观察归纳,第二种方式,只需要1次,是不是有很大的差别?
高斯的方法我也知道,但是遇到类似的问题…我们用的笨方法也是算法吗? 答:是的
好算法的标准
算法运行需要的时间,现代计算机,一秒能运算很多次,所以不能用秒来计量。相同计算机一次时间相对固定,不同配置的计算机又不相同。所以我们将执行次数作为时间复杂度。
int sum=0; //运行1次
int total=0; //运行1次
for(int 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) 来表示: T(n) = 2n2+3n+3 当n足够大的时候,例如n = 105 ,那么T(n) = 2 * 1010 + 3 *105 +3 可以看出,算法运行的时间主要取决于最高项,小项和常数可以忽略不计。 有些算法,如排序,查找、插入算法等,可以分为最好、最坏和平均情况分别去求算法的渐进复杂度。但是考察一个算法时,通常考察最坏的情况,最坏的情况对衡量算法好坏具有实际意义
算法占用的空间大小。 空间复杂度的本意指的是算法在运行过程中,占用了多少存储空间。算法占用的存储空间包括:
请分析如下的算法空间复杂度
void swap(int x,int y){ //交换x与y
int temp;
temp=x; //temp为辅助空间 ①
x=y; //②
y=temp; //③
}
两个数交换的过程:
这里使用了temp辅助变量,空间复杂度为O(1)
在递归算法中,每次递归都需要一个栈来保存调用记录,因此在计算递归的空间复杂度的时候,需要计算递归栈的深度。
int fac(int n){ //计算n的阶乘
if(n==0||n==1)
return 1;
else
return n*fac(n-1);
}
阶乘是典型的递归调用问题,递归包括地推和回归。递推是将原问题不断分解成子问题,直至满足结束条件,返回最近子问题的解。然后逆向逐一回归,最终到达递推开始的原问题,返回原问题的解。
思考:试求5的阶乘,程序将怎么计算呢? 5的阶乘的递推和回归的过程如下:
如上面两个图所示,递推、回归过程是从逻辑思维上推理,以图的方式形象的表达出来, 但计算机内部是怎样计算的呢?计算机使用一种称为“栈”的数据结构,“栈”类似放盘子的容器,每次从顶端放进去一个,拿出来的时候就只能从顶端拿,不允许从中间插入或抽取,因此称为“后进先出”
从图中可以看出,进栈,出栈的过程:子问题先被一步步压进栈,直至直接可解得到返回值,再一步步的出栈,最终得到返回值。在运算过程中,因为使用了n个栈作为辅助空间,因此阶乘的递归算法的空间复杂度为O(n)。时间复杂度也为O(n),因为n的阶乘仅比n-1的阶乘多了一次乘法运算,fac(n) = n * fac(n-1)。如果用T(n) 表示fac(n)的时间复杂度,则可以表示为 T(n) = T(n) + 1 =T(n-1) + 1 + 1 … = T(1) + …1 + 1 =n