一：算法的基本概念（1）数据结构和算法的关系

“数据结构”，“数据结构与算法”这样的词我们经常提到，甚至有的书就以它们作为名字，那么数据结构和算法究竟具有怎样的关系呢？

事实上，只谈数据结构是完全可以的，我们只需要用屈指可数的几篇文章就能全部讲解完毕，但是听完之后你可能没有任何感觉，或许有感觉——感觉没用。但是如果我们再把相应的算法拿出来讲一讲，你就会感叹到这些大佬怎么这么聪明。因此在数据结构中讲算法是为了帮助我们更好地理解，纯讲算法也会有相应的课程。当然算法要比数据结构难多了，从某种方面来讲它其实是数学问题的，可能受限于学习者的智商水平（别气馁，大家都一样，我们并不是大佬）

那什么是算法呢？ 我觉得历史上的一位大佬——高斯，就展现了算法的魅力

接触过C语言的同学都知道，计算1+2+…+100的程序应该这样编写

#include <stdio.h>int main(){	int i,sum=0	int n=0;	for(i=1;i<=n;i++)	{		sum*=i;	}	printf("%d\n",sum);}

我们认为它就是一种算法，因为它很明显已经解决了问题，但是高效吗？我认为高斯已经给出了答案

他的方法是

对应程序为

#include <stdio.h>int main(){	int i,sum=0	int n=100;	sum=(1+n)*n/2;	printf("%d\n",sum);}

它很明显也是一种算法，而且相较于之前的哪种方法来说，效率得到了很大的提升

（2）算法(Algorithm)的定义

算法(Algorithm)：是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作

王道视频课中讲到了一个例子，展示了算法就是解决问题的特定步骤的描述

从之前求和的例子我们可以看出：对于给定的问题可以有多种多样的算法来解决，只不过这些算法之间具有各自的优点和缺点二：算法的特性

有穷性：一个算法必须在执行有穷步之后结束，且每一步都可以在有穷时间内完成

注意区别程序，程序可以是无穷的

确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得到相同的输出

例如排序算法有很多种，但不论采用何种排序算法，最终结果是唯一确定的

可行性：一个算法所描述的操作都可以通过已经实现的基本运算执行次数来实现

可行性意味着算法可以转化为程序并上机运行并得到正确结果

输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合

输出：一个算法有一个或多个输入，这些输出是与输入有某种特定关系的输入

三：算法设计要求

正确性：是指算法至少应该具有输入、输出和加工处理且无歧义并能正确反映问题的需求，能够得到问题的正确答案。大体分为如下四个层次

算法程序没有语法错误算法程序对于合法的输入数据能够产生满足要求的输出结果算法程序对于非法的输入能够得出满足规格说明的结果算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果（最难达到）

可读性：算法设计的另一个目的就是为了便于阅读、理解和交流

可读性有助于人们理解算法，晦涩难懂的算法往往隐含错误，不容易被发现，并难于调试和修改，这一点在递归类的算法身上体会非常明显

健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或其它莫名其妙的结果

时间复杂度和空间复杂度较低：也就是说花的时间少而且占用内存空间小