第1章 算法概述

《第1章 算法概述》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机算法设计与分析（C第3版王晓东编著）山东科技大学信息学院计算机系杜玉越Office:J13-102Mobile:13864233609Email:yydu001@163.com1课程简介算法设计与分析是计算机科学技术、软件工程及相关专业的重要课程之一培养分析问题和解决问题的能力掌握算法设计的基本方法熟悉算法分析的基本技术为软件系统开发奠定扎实的理论基础2算法是计算机科学的重要研究领域之一应用领域不断扩大现代软件系统的核心“算法和数据结构”被列为计算学科的九个主题的第一个我国多数高校越来越重视算

2、法课程的教学分离算法与数据结构课程以算法设计策略为知识单元系统介绍算法的设计方法与分析技巧3主要参考书王晓东编著，计算机算法设计与分析（C语言版）（第3版），电子工业出版社，2004-7-1，25.50王晓东，算法设计与实验题解，电子工业出版社，2006-9-1，46.00（与C语言版第2版对应）王晓东编著，算法设计与分析（Java语言版），清华大学出版社，2003第1版，29.80T.H.Cormen,C.E.Leisersen,R.L.RivestandC.Stein.Introductiont

3、oAlgorithms.TheMITPress,secondedition,NewYork,McGraw-Hill,2001.（麻省理工学院出版社）（美）AnanyLevitin著，算法设计与分析基础（影印版），清华大学出版社，2003年第1版，39.004计算机专业学生能力培养学科人才的4大能力计算思维能力算法的设计与分析能力程序的设计与实现能力计算机系统的认知、分析、开发与应用能力学术型综合型工程型5计算机专业系列课程公共基础系列基础理论系列思维能力程序设计与算法的训练系列编程能力软件系统系列算

4、法能力(系统级的再认识与再提高)开发能力硬件技术系列实践系列与课程有机结合，构成整体，协调实现培养学科方法的应用、实践的体验与探索6体系结构网络通讯主干课程体系层次结构图高等代数数学分析程序设计数学分析计算方法汇编语言大学物理集合与图论概率与统计大学物理电路数理逻辑选修数学实验模拟电子数字数电近世代数数据结构与算法形式语言数据库操作系统编译原理软件工程计算机原理接口技术信号与系统选修学期基础理论软件系列硬件系列一二三四五六七7第1章算法概述学习要点:理解算法的概念理解什么是程序，程序与算法的区别和内

5、在联系掌握算法的计算复杂性概念掌握算法渐近复杂性分析方法及应用技术掌握用C++语言描述算法的方法8算法(Algorithm)算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入：有外部提供的量作为算法的输入(2)输出：算法产生至少一个量作为输出(3)确定性：组成算法的每条指令是清晰、无歧义的(4)有限性：算法中每条指令的执行次数是有限的，每条指令的执行时间也是有限的。9程序(Program)程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)有限性。

6、例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序，通过特定的算法来实现。该子程序得到输出结果后便终止。10问题求解(ProblemSolving)证明正确性分析算法设计程序理解问题问题建模与符号描述选择数据结构算法设计策略设计算法11算法复杂性分析算法复杂性=算法运行所需的计算机资源的量算法的时间复杂性T(n)－所需的时间资源的量，其中n是问题的规模（输入大小）算法的空间复杂性S(n)－所需的空间资源的量主要讨论时

7、间复杂性,空间复杂性分析相对比较简单,计量方法相似.12算法的时间复杂性最坏情况下的时间复杂性：Tmax(n)=max{T(I)

8、size(I)=n}最好情况下的时间复杂性：Tmin(n)=min{T(I)

9、size(I)=n}平均情况下的时间复杂性：Tavg(n)=其中I是问题的规模为n的实例，p(I)是实例I出现的概率。13算法渐近复杂性通常，T(n),asn;If(T(n)-t(n))/T(n)0，asn，则称t(n)是T(n)的渐近性态，或为算法的渐近复杂性。在数学上，t(n)

10、是T(n)的渐近表达式，是T(n)略去低阶项留下的主项，比T(n)简单。分析算法复杂性的目的：比较求解同一问题的两个不同算法的效率。因此，只要得到不同t(n)的阶即可。14渐近分析的记号设对所有n，存在正函数f(n)0，g(n)0。渐近上界记号OO(g(n))={f(n)

11、存在正常数c和n0使得对所有nn0有：0f(n)cg(n)},记为f(n)＝O(g(n))，或说f(n)的阶不高于g(n)的阶asn。渐近下界记号(g(n))={f(n)

12、存在正常