🔝算法学习 【第一周】Ⅰ

一、前言

这段时间我又参加了一个CSDN活动——14天阅读挑战赛，今天这个活动正式开始，活动内容是阅读指定书籍**《趣学算法 第2版》**然后写相关内容的博客连续两周打卡即可，所以接下来的两周我将更新打卡有关算法方面的知识，后续活动结束之后我也会继续保持每周更新的。

算法一直都是我最薄弱的地方，所以正好趁这个机会弥补一下自己的弱项，提高自己。

程序=数据结构+算法，数据结构是程序的骨架，算法是程序的灵魂，所以作为计算机人，熟练的掌握常用算法非常重要，而且以后行业内搞算法最吃香。

算法门槛比较高，所以作为初学者的我们慢慢来了解学习。

注意：博客中大部分代码都会使用伪代码进行表示，少数使用程序的时候会进行标注！

二、算法是什么？

算法是对特定问题求解步骤的一种描述。举个例子：

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

-1，1，-1，1，…，（-1）ⁿ

看见这个题目，大部分人可能会这样去做：

int sum1 (int n){
	int sum=0;
	for(int i=1;i<n;i++)
		sum+=pow(-1,i);		//表示（-1）^i
	retun sum;
}

这个方法可以求和，但我们可以使用更好的算法：

int sum2(int n){
	int sum=0;
	if(n%2==0)
		sum=0;
	else
		sum=-1;
	retun sum;
}

这两种都能称为算法，但我们写程序的时候肯定要选择最好的算法，上面第二种算法跟高斯计算1~100的和使用的算法一样，第一种算法需要运行n+1次，而第二种算法只需要运算1次。

三、算法的特性

算法具有以下特性：

1. 有穷性：算法是由若干条指令组成的有穷序列，总是在执行若干次后结束，不能永不停止。
2. 确定性：每条语句都有确定的含义，无歧义。
3. 可行性：算法在当前环境条件下可以通过有限次运算来实现。
4. 输入和输出：有零个或者多个输入以及一个或多个输出。

四、好的算法的评判标准

1. 正确性：算法能满足具体问题的需求，程序能正常运行，没有语法错误，能通过典型软件测试，并且能达到预期。
2. 易读性：算法遵循标识符命名规则，简洁易懂，注释语句恰当适量，方便阅读，便于后期调试和修改。
3. 健壮性：算法对非法数据及操作有较好的反应和处理，能对一些错误的操作进行提示。
4. 高效性：算法运行效率要高，也就是运行时间短。
5. 低存储性：算法所需的存储空间小，算法占用的空间大小又被称为空间复杂度。

五、算法复杂性

一般的算法都会具备前三条，所以我们重点关注一下后面两条，也就是算法的时间复杂度和空间复杂度，这是衡量一个算法好坏的重要标准。

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次
}

我们把所有的运行次数加起来，就可以表示为：T(n)=2n²+3n+3

当n足够大的时候，运行的时间主要取决于最高项，其他的项和常数可以忽略不计，也就是说上面的算法时间复杂度是：O(n²)

我们再举一个例子看看：

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

对于上面算法我们无法立即确定while中程序运行了多少次，所以我们可以进行假设，假设它运行了x次，然后找程序运行的规律，程序运行：2，2²，2³，…，2^x。所以程序在2^x=n时结束，也就是说$x={\log }_{2}n$，总的运行次数是：$1+2{\log }_{2}n$，所以时间复杂度也就是O(${\log }_{2}n$)。

但并不是所有的算法都能直接计算运行次数，算法可能1次就成功，也可能n次才能成功，一般来说，考察一个算法的时间复杂度，一般都是考察最坏的情况，而不是考察最好的情况。

2、空间复杂度

空间复杂度就是算法占用的空间大小，算法占用的存储空间包括：

• 输入和输出数据
• 算法本身
• 额外需要的辅助空间

前两项一般都是固定的，所以一般衡量一个算法的空间复杂度主要看算法在运行时所使用的辅助变量占用的空间。

举个例子：

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的阶乘，进栈出栈过程如下：

可以看出在运算过程中，如果是n的阶乘，我们使用了n个栈空间作为辅助空间，因此阶乘递归算法的空间复杂度是O(n)，其时间复杂度也是O(n)。

六、最后我想说

第一周第一次打卡，我们主要了解算法，算是入门学习，主要了解学习了有关算法的时间复杂度和空间复杂度，接下来第二次打卡我们将通过两个例子了解学习一下有关算法的设计和改进，请大家稍安勿躁，谢谢。

另外，我还想说的是，如果你想知道如何使用Markdown编写常用的数学公式的话，推荐你去看一下这篇博客，记住其中常用的几个公式即可，可以大大提高我们写博客或者总结学习的效率。

Markdown- 常用数学公式

最后，谢谢大家能看完，我也会继续加油的。