什么是算法呢?算法是描述解决问题的方法。算法(Algorithm)这个单词最早出现在波斯数学家阿勒·花刺子密在公元825年(相当于我们中国的唐朝时期)所写的《印度数字算术》中。如今普遍认可的对算法的定义是:算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。
为了解决某个或某类问题,需要把指令表示成一定的操作序列,操作序列包括一组操作,每一个操作都完成特定的功能,这就是算法了。
1.1、数据结构与算法的关系
“今天是你女友生日,你打算请女友去看爱情音乐剧,到了戏院,抬头一看——《梁山伯》18:00开演。嗯,怎么会是这样?一问才知,今天饰演祝英台的演员生病,所以梁山伯唱独角戏。真是搞笑了,这还有什么看头。于是你们打算去看爱情电影。到了电影院,一看海报——《罗密欧》,是不是名字写错了,问了才知,原来饰演朱丽叶的演员因为嫌弃演出费用太低,中途退演了。制片方考虑到已经开拍,于是就把电影名字定为《罗密欧》,主要讲男主角的心路旅程。哎,这电影还怎么看啊?
事实上,数据结构和算法也是类似的关系。只谈数据结构,当然是可以,我们可以在很短的时间就把几种重要的数据结构介绍完。听完后,很可能你没什么感觉,不知道这些数据结构有何用处。但如果我们再把相应的算法也拿来讲一讲,你就会发现,甚至开始感慨:哦,计算机界的前辈们,的确是一些很牛很牛的人,他们使得很多看似很难解决或者没法解决的问题,变得如此美妙和神奇。”
摘录来自: 程杰. “大话数据结构。”
1.2、两种算法的比较
大家都已经学过一门计算机语言,不管学的是哪一种,学得好不好,好歹是可以写点小程序了。现在我要求你写一个求1+2+3+......+100结果的程序,你应该怎么写呢?
大多数人会马上写出下面的C语言代码(或者其他语言的代码):
int i, sum = 0, n = 100;
for (i = 1; i <= n; i++) {
sum = sum + I;
}
printf("%d", sum);
这是最简单的计算机程序之一,它就是一种算法,我不去解释这代码的含义了。问题在于,你的第一直觉是这样写的,但这样是不是真的很好?是不是最高效?
这里我们不得不提到一个伟大的数学家对这个题目的解答:

这就是著名的高斯算法。
用我们的计算机程序来实现如下:
int sum = 0,n = 100;
sum = (1 + n) * n / 2;
printf("%d", sum);
1.3、算法特性
算法具有五个基本特性:输入、输出、有穷性、确定性、可行性。
1.3.1、输入输出
输入和输出特性比较容易理解,算法具有零个或多个输入。尽管对于绝大多数算法来说,输入参数都是必要的,但对于个别情况,如打印“helloworld!”这样的代码,不需要任何输入参数,因此算法的输入可以是零个。算法至少有一个或多个输出,算法是一定需要输出的,不需要输出,你用这个算法干吗?输出的形式可以是打印输出,也可以是返回一个或多个值等。
1.3.2、有穷性
有穷性:指算法在执行有限的步骤之后,自动结束而不会出现无限循环,并且每一个步骤在可接受的时间内完成。
1.3.3、确定性
确定性:算法的每一步都有确定的意义,不会出现歧义。也就是说,相同的输入只会有相同的输出。
1.3.4、可行性
可行性:也就是说算法的每一步都可以通过有限次数的运行来得到一个正确的结果。
1.4、算法的设计要求
1.4.1、正确性
正确性:算法的正确性是指,算法至少应该具有输入、输出。能够处理问题,正确的处理需求。
算法的正确性大概可以分为四个部分:
- 算法的程序设计没有语法错误。如果语法有错误,那么连编译都无法通过,又何谈执行呢?
- 算法对程序合法的输入能够输出正确的结果。
- 算法对于非法的输入,能够给出合理的说明。
- 算法对于精心选择的或者刁钻的测试数据,都要有满足要求的输出结果。
1.4.2、可读性
可读性:算法设计的另一目的是为了便于阅读、理解和交流。
如果可读性不好,时间长了自己都不知道写了些什么。可读性是算法(也包括实现它的代码)好坏很重要的标志。
1.4.3、健壮性
一个好的算法还应该能对输入数据不合法的情况做合适的处理。比如输入的时间或者距离不应该是负数等。
健壮性:当输入数据不合法时,算法也能做出相关处理,而不是产生异常或莫名其妙的结果。
1.4.4、时间效率高和存储量低
好的算法还应该具备时间效率高和存储量低的特点。
时间效率高是指,能够在最短的时间内得出有效的结果。
存储量低是指,在计算的过程中,所占用的内存最少。
网友评论