PDF《第2章算法》

18 世纪生于德国小村庄的高斯,上小学的一天,课堂很乱,就像我们现在下 面那些窃窃私语或者拿着手机不停摆弄的同学一样,老师非常生气,后果自然也很严 重.于是老师在放学时,就要求每个学生都计算 1+2+…+100 的结果,谁先算出来谁 先回家.? 天才当然不会被这样的问题难倒,高斯很快就得出了答案,是5050.老师非常惊 讶,因为他自己想必也是通过 1+2=3,3+3=6,6+4=10,……,4950+100=5050 这样 算出来的,也算了很久很久.说不定为了怕错,还算了两三遍.可眼前这个少年,为 何可以这么快地得出结果?? 19? ? 数据结构 大话 高斯解释道:? 用程序来实现如下:? int i, sum = 0,n = 100;

sum = (1 + n) * n / 2;

printf( %d , sum);

神童就是神童,他用的方法相当于另一种求等差数列的算法,不仅仅可以用于

1 加到 100,就是加到一千、一万、一亿(需要更改整型变量类型为长整型,否则会溢 出) ,也就是瞬间之事.但如果用刚才的程序,显然计算机要循环一千、一万、一亿次 的加法运算.人脑比电脑算得快,似乎成为了现实.? 2.4 算法定义 什么是算法呢?算法是描述解决问题的方法.算法(Algorithm)这个单词最早出 现在波斯数学家阿勒・花刺子密在公元

825 年(相当于我们中国的唐朝时期)所写的 《印度数字算术》中.如今普遍认可的对算法的定义是:? 算法是解决特定问题求解步骤的描述,在计算机中表现为指令的 有限序列,并且每条指令表示一个或多个操作. 刚才的例子我们也看到,对于给定的问题,是可以有多种算法来解决的.? 那我就要问问你们,有没有通用的算法呀?这个问题其实很弱智,就像问有没有 可以包治百病的药呀!? 现实世界中的问题千奇百怪,算法当然也就千变万化,没有通用的算法可以解决 所有的问题.甚至解决一个小问题,很优秀的算法却不一定适合它.? 算法定义中,提到了指令,指令能被人或机器等计算装置执行.它可以是计算机 指令,也可以是我们平时的语言文字.? 20? 第2章算法 为了解决某个或某类问题,需要把指令表示成一定的操作序列,操作序列包括一 组操作,每一个操作都完成特定的功能,这就是算法了.? 2.5 算法的特性 算法具有五个基本特性:输入、输出、有穷性、确定性和可行性.? 2.5.1 输入输出 输入和输出特性比较容易理解,算法具有零个或多个输入.尽管对于绝大多数算 法来说,输入参数都是必要的,但对于个别情况,如打印 hello world! 这样的代 码,不需要任何输入参数,因此算法的输入可以是零个.算法至少有一个或多个输 出,算法是一定需要输出的,不需要输出,你用这个算法干吗?输出的形式可以是打 印输出,也可以是返回一个或多个值等.? 2.5.2 有穷性 有穷性:指算法在执行有限的步骤之后,自动结束而不会出现无限循环,并且每 一个步骤在可接受的时间内完成.现实中经常会写出死循环的代码,这就是不满足有 穷性.当然这里有穷的概念并不是纯数学意义的,而是在实际应用当中合理的、可以 接受的 有边界 .你说你写一个算法,计算机需要算上个二十年,一定会结束,它在 数学意义上是有穷了,可是媳妇都熬成婆了,算法的意义也不就大了.? 2.5.3 确定性 确定性:算法的每一步骤都具有确定的含义,不会出现二义性.算法在一定条件 下,只有一条执行路径,相同的输入只能有唯一的输出结果.算法的每个步骤被精确 定义而无歧义.? 2.5.4 可行性 可行性:算法的每一步都必须是可行的,也就是说,每一步都能够通过执行有限 次数完成.可行性意味着算法可以转换为程序上机运行,并得到正确的结果.尽管在 目前计算机界也存在那种没有实现的极为复杂的算法,不是说理论上不能实现,而是 21? ? 数据结构 大话 因为过于复杂,我们当前的编程方法、工具和大脑限制了这个工作,不过这都是理论 研究领域的问题,不属于我们现在要考虑的范围.? 2.6 算法设计的要求 刚才我们谈到了,算法不是唯一的.也就是说,同一个问题,可以有多种解决问 题的算法.这可能让那些常年只做有标准答案题目的同学失望了,他们多么希望存在 标准答案,只有一个是正确的,把它背下来,需要的时候套用就可以了.不过话说回 来,尽管算法不唯一,相对好的算法还是存在的.掌握好的算法,对我们解决问题很 有帮助,否则前人的智慧我们不能利用,就都得自己从头研究了.那么什么才叫好的 算法呢?? 嗯,没错,有同学说,好的算法,起码要是正确的,连正确都谈不上,还谈什么 别的要求?? 2.6.1 正确性 正确性:算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、 能正确反映问题的需求、能够得到问题的正确答案.? 但 .算法程序没有语法错误.? 是算法的 正确 通常在用法上有很大的差别,大体分为以下四个层次.?