算法与程序设计：第1章-算法基础.ppt

算法与程序设计算法初步算法学习的重要性算法学习的必要性算法学习的必要性1．课程学时
总学时:48学时;讲课:36学时;上机:12学时
上机时间：第6、8、10、12、14、16周
2．本课程主要参考书
[1]王晓东.计算机算法设计与分析.电子工业出版社
[2]软件设计师教程课前简介课前简介课程内容第1章算法基础第1章算法基础1.1算法(Algorithm)算法通常指可以用来解决的某一类问题的步骤，这些步骤必须是明确的和有效的，而且能够在有限步之内完成的。“算法”的大陆中文名称出自公元前1世纪成书的《周髀算经》；
英文名称Algorithm来自于9世纪波斯数学家al-Khwarizmi；
欧几里得算法被人们认为是史上第一个算法。
2.算法的性质可行性：算法中描述的操作都可通过有限次的基本运算来实现。
确定性：算法中每个步骤含义明确，无二义性。
有穷性：一个算法必须保证在有限个操作步骤执行后终止。
输入：一个算法应具有零个或多个输入。
输出：一个算法应具有一个或多个输出。
自然语言就是人们日常使用的语言，可以是汉语或英语或其它语言。
除了那些很简单的问题外，一般不用自然语言描述算法。1.1算法(Algorithm)1.1算法(Algorithm)1.1算法(Algorithm)令士兵从1～3报数，结果最后一个士兵报2；【例1】韩信点兵【例1】韩信点兵算法描述最初记述这类算法的是一本名叫《孙子算经》的书。
这类算法的名称也很多，宋朝周密叫它“鬼谷算”，又名“隔墙算”；杨辉叫它“剪管术”；而比较通行的名称是“韩信点兵”。
这在数学史上是极有名的问题，外国人一般把它称为“中国剩余定理”。【例2】求1+2+3+4+5+6累加和算法2.可以运用下面公式直接计算.4.算法举例如果题目改为：求1×3×5×……×1000：Jiechen(n)
p←1
i←2
whilei<=n
dop←p*i
i=i+1
returnp5.程序（program）6.冒泡排序（bubblesort）6.冒泡排序（bubblesort）6.冒泡排序（bubblesort）6.冒泡排序（bubblesort）7.算法正确性证明1.2算法分析1.2算法分析1.算法分析的基本法则2.冒泡排序算法分析3.不同情况下的算法时间复杂度3.不同情况下的算法时间复杂度算法最坏情况下的运行时间是任一输入运行时间的上界并且经常出现，所以对一个算法我们关心的是最坏情况下的时间复杂度。1.3算法的运行时间1.3算法的运行时间1.算法渐近复杂性2.渐近表示（3）紧渐近界记号
(g(n))={f(n)|存在正常数c1,c2和n0使得对所有nn0有：c1g(n)f(n)c2g(n)}

3.算法分析中常见的复杂性函数小规模数据大规模数据4.算法分类第1章算法基础练习练习练习习题