《算法与数据结构》PPT课件

《《算法与数据结构》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章算法与数据结构16学时算法与数据结构目的与要求：掌握算法与算法设计基本方法掌握数据结构的表示与基本操作重点与难点：算法描述方法及应用数据结构及其表示方法查找与排序算法设计本章要点算法与数据结构4.1算法及其表示4.2常用算法结构分析4.3数据结构及表示2学时4.4常用数据结构及表示（表、树、图）6学时4.5查找与排序4学时4.6文件与文件操作2学时4.7应用举例2学时本章内容2学时算法历史小知识算法的中文名称出自周髀算经；而英文名称Algorithm来自于9世纪波斯数学家比阿勒.霍瓦里松的名字al-Khwarizmi，因为比阿勒.霍瓦里松在数学

2、上提出了算法这个概念。他写的书《al-jabrw’almuqabalah》(代数学)演变成为现在中学的代数教科书。Ad-Khwarizmi强调求解问题是有条理的步骤。如果他能活到今天的话，他一定会被以他的名字而得名的方法的进展所感动。“算法”原为“algorism”，意思是阿拉伯数字的运算法则，在18世纪演变为“algorithm”。第一次编写算法是AdaByron于1842年为巴贝奇分析机编写求解解伯努利方程的程序，因此AdaByron被大多数人认为是世界上第一位程序员。20世纪的英国数学家图灵提出了著名的图灵论题，并提出一种假想的计算机的抽象模型

3、，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要的作用4.1算法及其表示算法就是一种解题的方法，是解题过程的精确描述。算法是由若干条指令组成的有穷序列。即由有限条可完全执行的，有确切含义的指令（或命令，语句）所构成。算法通俗说法算法严格说法算法五大特征有穷性一个算法必须总是在执行有穷步后结束，且每一步都可在有穷时间内完成；确定性算法中的每一个指令比须有明确的含义，不能有二义性；可行性算法中描述的操作都是可通过已经实现的基本运算、执行有限次实现的；输入一个算法应有0个或多个输入；输出一个算法应有1个或多个输出。

4、算法的表示自然语言流程图特定的表示算法的图形符号伪语言包括程序设计语言的三大基本结构及自然语言的一种语言类语言类似高级语言的表示，例如类PASCAL、类C语言算法的描述插入排序Insertion-Sort(A)1forj=1ton-12key=A[j]3i=j-14whilei>=0andA[i]>key5A[i+1]=A[i]6i=i-17A[i+1]=keyj=1j=2j=3j=4j=5245613245613245663245563244563224563124563A[0]A[1]A[2]A[3]A[4]A[5]算法的分析与评价1）正

5、确性（Correctness）2）可读性（Readability）3）健壮性（robustness）4）高效率与低存储量算法的评价标准应具有容错处理功能。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。处理速度快；存储容量小。时间和空间是矛盾的、实际问题的求解往往是求得时间和空间的统一、折中。算法的第一目的是为了阅读和交流；可读性有助于对算法的理解；可读性有助于对算法的调试和修改。程序不含语法错误；程序对几组输入数据程序对精心选择的、典型的、苛刻的、带有刁难性的几组输入数据；程序对一切合法的输入数据能产生满足规格要求的结果算法的复

6、杂性一个算法花费的时间与算法中语句的执行次数成正比，计算一个算法的时间复杂度一般用语句执行次数的数量级来衡量。数据结构中数据元素个数n称为问题的规模，当n不断变化时，语句的执行次数也会变化。时间复杂度空间复杂度问题的规模空间复杂度是指算法在计算机内执行时所占用的内存开销规模。但一般讨论的是除正常占用内存开销外的辅助存储单元规模。时间或空间单位下数据的量的多少。空间单位一般规定为一个简单变量（如整型、实型等）所占存储空间的大小；时间单位则一般规定为执行一个简单语句（如赋值语句、判断语句等）所用时间。时间复杂度表示通常用“阶”“O（数量级）”来表示。常见

7、的时间复杂度有：O（1）常数阶；O（logn）对数阶；O（n）线性阶；O（n＾2）平方阶。例如：for(i=1;i<=n;i++)for(j=1;j<=i;j++)d[i][j]=data[i][j]+1;问题规模与时间复杂度的关系一般来说，计算机算法是问题规模n的函数f(n)，算法的时间复杂度也因此记做$T(n)=mathcal\{O\}(f(n))$因此，问题的规模n越大，算法执行的时间的增长率与f(n)的增长率正相关，称作渐进时间复杂度（AsymptoticTimeComplexity）。算法与建模算法/解题策略计算模型。常

8、用三种计算模型：数学模型简单、准确，有成熟的计算方法。过程模拟模型处理日常事务问题算法的模型，模型简单易行。