计算机算法基础1

2020/1/23序专业基础课程：数据结构、计算机语言操作系统、编译如何编写计算机程序：数据结构+算法=程序算法：计算机软件的“灵魂”算法是计算机科学和计算机应用的核心2020/1/23教材：计算机算法基础余祥宣等编著华中科技大学出版社参考书：算法设计与分析王晓东编著清华大学出版社计算机算法导引——设计与分析卢开澄编著清华大学出版社IntroductionToAlgorithm高教出版社，MITPress学时：32+8学时2020/1/23章节安排第一章导引与基本数据结构√第二章分治法√第三章贪心方法√第四章动态规划√第五章检索与周游√第六章回溯法⊙第七章分枝-限界⊙第八章NP-问题?2020/1/23第一章导引与基本数据结构1.1算法的定义及特性1.什么是算法？★算法如数字、计算一样，是一个基本概念。★算法是解一确定类问题的任意一种特殊的方法。★在计算机科学中，算法是使用计算机解一类问题的精确、有效方法的代名词；算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。2020/1/232.算法的五个重要特性确定性、能行性、输入、输出、有穷性1）确定性：算法的每种运算必须要有确切的定义，不能有二义性。例：不符合确定性的运算5/0将6或7与x相加未赋值变量参与运算2020/1/232）能行性算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在“有限”的时间内完成。例：整数的算术运算是“能行”的实数的算术运算是“不能行”的2020/1/233）输入每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合——定义域（或值域）4）输出一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量。2020/1/235）有穷性一个算法总是在执行了有穷步的运算之后终止。计算过程：只满足确定性、能行性、输入、输出四个特性的一组规则。算法和计算过程的区别：计算过程：操作系统(不终止的运行过程)算法是“可以终止的计算过程”算法的时效性：只能把在相当有穷步内终止的算法投入到计算机上运行2020/1/234.我们的主要任务算法学习将涉及5个方面的内容：1）设计算法：创造性的活动2）表示算法：思想的表示形式，SPARKS语言3）确认算法：证明算法对所有可能的合法输入都能得出正确的答案。算法证明：证明算法的正确性，与语言无关程序证明：证明程序的正确性4）分析算法：对算法的时、空特性做定量分析，以了解算法的好坏5）测试程序：调试：“调试只能指出有错误，而不能指出它们不存在错误”作时空分布图：验证分析结论，优化算法设计本课程集中于学习算法的设计与分析。通过学习，掌握计算机算法设计和分析基本策略与方法，为设计更复杂、更有效的算法奠定基础2020/1/235.课程关系数据结构程序设计语言：结构化设计数学基础非数值计算领域的基本知识2020/1/231.2分析算法1.分析算法的目的在于：通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。算法分析是计算机领域的“古老”而“前沿”的课题。2020/1/232.重要的假设和约定1）计算机模型的假设计算机形式理论模型：Turing机模型通用计算机模型：顺序计算机有足够的“内存”能在固定的时间内存取数据单元2020/1/232）计算的约定算法的执行时间=∑fi*ti其中，fi是算法中用到的某种运算i的次数——称为该运算的“频率计数”ti是该运算执行一次所用的时间——与程序语言和硬件有关确定：使用何种运算及其执行时间。从运算的“时间特性”上将运算的分类：时间囿界于常数的运算：·基本算术运算，如整数、浮点数的加、减、乘、除·字符运算、赋值运算、过程调用等特点：尽管每种运算的执行时间不同，但一般只花一个固定量的时间（单位时间）就可完成。2020/1/232）计算的约定（续）其他运算：·字符串操作：与字符串中字符的数量成正比·记录操作：与记录的属性数、属性类型等有关特点：运算时间无定量。如何分析非时间囿界于常数的运算：分解成若干时间囿界于常数的运算。如：tstring=Length（String）*tchar2020/1/233）工作数据集的选择编制能够反映算法在最好、平均、最坏情况下工作的数据配置。然后使用这些数据配置运行算法，以了解算法的性能。编制测试数据是程序测试与算法分析中的关键技术之一。·作为算法分析的数据集：反映算法的典型特征·作为程序正确性及性能测试的数据集：测试程序的对错，反映对性能指标产生影响的方面,如边界值2020/1/233.如何进行算法分析？对算法进行全面分析，可分两个阶段进行：事前分析：求算法的一个时间/空间限界函数，即通过对算法的“理论”分析，得出关于算法时间和空间特性的特征函数（Ο、Ω）——与计算机物理软硬件没有直接关系。事后测试：将算法编制成程序后实际放到计算机上运行，收集其执行时间和空间占用等统计资料，进行分析判断——直接与物理实现有关。2020/1/231）事前分析目的：试图得出关于算法特性的一种形式描述，以“理论上”衡量算法的“好坏”。如何给出反映算法特性的描述？统计算法中各种运算的执行情况，包括：引用了哪些运算每种运算被执行的次数该种运算执行一次所花费的时间等。算法的执行时间=∑fi*ti2020/1/23频率计数频率计数：算法中语句或运算的执行次数。例：x←x+yfori←1tondofori←1tondox←x+yforj←1tondorepeatx←x+yrepeatrepeat(a)(b)(c)分析：(a)：x←x+y执行了1次(b)：x←x+y执行了n次(c)：x←x+y执行了n2次2020/1/23一条语句在整个程序运行时实际执行时间=频率计数*每执行一次该语句所需的时间在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立一种理论上分析模型。2020/1/23数量级——衡量频率计数的“大小”的一种测度语句的数量级：语句的执行频率例：1，n，n2算法的数量级：算法所包含的所有语句的执行频率之和。数量级反映了算法复杂度的最本质的特征。例：假如求解同一个问题的三个算法分别具有n，n2，n3数量级。若n=10，则可能的执行时间将分别是10，100，1000个单位时间——与环境因素无关。2020/1/23频率计数的函数表示就计算时间而言，事前分析阶段求得算法在频率计数上的函数表示——与规模n有关的函数形式，记为：g(n)★不同的算法，g(n)的具体形式是不同的，如logn，nlogn，n2等★g(n)的一般形式：关于n的简单函数式“实际”能够得到的：1)函数式的最高次项2)最高次项与函数整体的关系。空间特性分析（与时间特性的分析类似，略）2020/1/232）事后测试目的：运行程序，统计执行实际耗费的准确的时间与空间，与事前分析的结论进行比较，验证先前的分析结论——包括正确性、执行性能等，比较、优化所设计的算法。分析手段：作时、空性能分布图2020/1/234.计算时间的渐近表示记：算法的实际计算时间为f(n)，计算时间的限界函数为g(n)其中，n是输入或输出规模的某种测度。f(n)表示算法的“实际”执行时间—与机器及语言有关。g(n)是事前分析的结果——一个形式简单的函数，如nm，logn，2n，n!等。是与频率计数有关、而与机器及语言无关的函数。以下给出算法执行时间：上界（О）、下界（Ω）、“平均”（）的定义。2020/1/231）上界函数定义1如果存在两个正常数c和n0，对于所有的n≥n0，有|f(n)|≤c|g(n)|则记作f(n)=Ο(g(n))含义：如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个上界函数。f(n)的数量级就是g(n)。试图求出最小的g(n)，使得f(n)=Ο(g(n))。2020/1/23多项式定理定理1若A(n)=amnm+…+a1n+a0是一个m次多项式，则有A(n)=Ο(nm)即：变量n的固定阶数为m的任一多项式，与此多项式的最高阶nm同阶。证明：取n0=1,当n≥n0时，有|A(n)|≤|am|nm+…+|a1|n+|a0|≤(|am|+|am-1|/n+…+|a0|/nm)nm＝(|am|+|am-1|+…+|a0|)nm令c=|am|+|am-1|+…+|a0|则，定理得证。2020/1/23计算时间的数量级的大小对算法的有效性有决定性的影响例：假设解决同一个问题的两个算法，它们都有n个输入,计算时间的数量级分别是n2和nlogn。则，n=1024：分别需要1048576和10240次运算。n=2048：分别需要4194304和22528次运算。分析：★同等规模下的计算量比较：★规模增大情况下的比较：在n加倍的情况下，一个Ο(n2)的算法计算时间增长4倍，而一个Ο(nlogn)算法则只用两倍多一点的时间即可完成。2020/1/23多项式时间算法和指数时间算法多项式时间算法：可用多项式（函数）对其计算时间限界的算法。常见的多项式限界函数有：Ο(1)Ο(logn)Ο(n)Ο(nlogn)Ο(n2)Ο(n3)指数时间算法：计算时间用指数函数限界的算法常见的指数时间限界函数：Ο(2n)Ο(n！)Ο(nn)说明：当n取值较大时，指数时间算法和多项式时间算法在计算时间上非常悬殊。2020/1/23典型的计算时间函数曲线2020/1/23一般认识当数据集的规模很大时，要在现有的计算机系统上运行具有比Ο(nlogn)复杂度还高的算法是比较困难的。指数时间算法只有在n取值非常小时才实用。要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度，而不是（仅仅依靠）提高计算机的速度。2020/1/23计算时间函数值比较32020/1/23定义1.2如果存在两个正常数c和n0，对于所有的n≥n0，有|f(n)|≥c|g(n)|则记作f(n)=Ω(g(n))含义：如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是不小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个下界函数。试图求出“最大”的g(n)，使得f(n)=Ω(g(n))。2）下界函数2020/1/23定义1.3如果存在正常数c1，c2和n0，对于所有的n≥n0，有c1|g(n)|≤|f(n)|≤c2|g(n)|则记作含义：算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。可看作：既有f(n)=Ω(g(n))，又有f(n)=Ο(g(n))))(()(ngnf3）“平均情况”限界函数2020/1/234）限界函数的性质1）若且，则。即О具有传递性。（同）2）当且仅当3）若，则。即，定义了一个等价关系（等价类）证明：从定义出发。证明过程略。)(gf)(hg)(hf、)(fg)(gf)(fg)(gf2020/1/235.常用的整数求和公式在算法分析中，在统计语句的频率时，求和公式的一般形式为：如：h(n)i)()(ngif)(11knikni2020/1/231.3关于SPARKS语言本书为描述算法选用的一种计算机语言类PASCAL语言结构化设计2020/1/231.基本语法成分1）数据类型整型integer实型float布尔型boolean字符型char2）变量声明类型说明符变量；integeri,j;booleanb;charc3）数组任意整数下标integerA(1:5,7:20)integerB(5,7:20)2020/1/234）赋值运算（变量）←（表达式）x←2+x;5）逻辑运算：andornot6）关系运算：＜≤＝≠≥＞2020/1/237）控制结构：顺序:（略）分支:·ifconditionthen