【精品】算法分析与设计

《【精品】算法分析与设计》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、题型问答题填空题计算题算法设计题1.1算法1什么是算法？算法是解一确定类问题的任意一种特殊的方法。在计算机科学屮，算法是使用计算机解一类问题的粘确、有效方法的代名词:算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。2.算法的五个重要特性确定性、能行性、输入、输出、有穷性侑限性3）输入每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合——定义域计算过程：只满足确定性、能行性、输入、输出四个特性但不一定能终I上的-•组规则。准确理解算法和计算过程的区别：>不能终止的计算过程：操

2、作系统>算法是“可以终止的计算过程"。>算法的时效性：只能把在相当有穷步内终止的算法投入到计算机上运行。1.2算法描述算法=控制结构+原操作表示算法的语言主要有：■自然语言■流程图■盒图■PAD图■伪代码■计算机程序设计语言本书中的算法描述约定■采用类似C语言的伪代码描述法顺序结构：以“；”结束选择结构：if,switch循环结构：for,while,doi-while■数据类型:int,float,double,char■数组：类型名数组名[n];下标以0开始■模块及接口:main（）开始return（返回信息）1.

3、算法分析的目的通过对算法分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好算法，改进差算法，避免无益的人力和物力浪费。2.重要的假设和约定1）计算机模型的假设■计算机形式理论模烈：Turing机模型■通用计算机模型：>单处理器：每次执行程序中-•条指令>有足够的“内存">能在固定的时间内存取数据单元2）计算的约定■确定使用什么样的运算及其执行时间。■从计算时间上，运算的分类：>时间囿界于常数的运算：每种运算的执行时间不同，但一•般只花一个固定量吋间（单位时间）就可完成。iO基本算术运算

4、iO字符运算i0赋值运算i0过程调用等2）计算的约定>其他运算：特点：运算时间无定量iCS字符串操作：与字符串屮字符的数量成正比。iO记录操作：与记录的属性数、属性类型等有关。如何分析非时间I冇1界于常数的运算？如：Tslring=Length（String）*tchar■算法的执行时间二EFi%是算法屮用到的某种运算i的次数，匕是该运算执行一次所用时间。3）工作数据集的选择■编制能够反映算法在最好、平均、最坏情况卜•工作的数据配置。然后使用这些数据配置运行算法，以了解算法的性能。■测试数据集的生成在冃前算法证明与程序

5、正确性证明没有収得理论上的突破性进展的情况下，是程序测试与算法分析中的关键技术之一。iO作为算法分析的数据集：典型特征i0作为程序性能测试的数据集：对执行指标产牛影响的性质4.如何进行算法分析？■事前分析：就算法本身，通过对其执行性能的理论分析，得出关于算法特性——时间和空间的一个特征函数（0、Q）—与计算机软破件没有直接关系。■事后测试：将算法编制成程序后放到计算机上运行，收集其执行时间和空间占用等统计资料，进行分析判断——直接与物理实现有关。1）事前分析■目的：试图得出关于算法执行特性的一种形式描述，以“理论上'衡

6、量算法“好坏”。■如何给出反映算法执行特性的描述？最直接方法：统计算法屮各种运算的执行情况：>运用了哪些运算>每种运算被执行的次数>该种运算执行一次所花费的吋间算法的执行时间=EFj*ti算法的输入规模■算法的执行吋间随问题规模的増长而增长，增长的速度随不同的并法而不同■没有一个方法可以准确的计算算法的具体执行时间语言、编译系统、计算机■实际上，在评估算法的性能时，并不需耍对算法的执行时间作出准确的统计，人们希望算法与实现的语言无关、与执行的计算机无关■所关心的是：算法的执行时间，随着输入规模的增长而增长的情况■计算时

7、间/频率计数的表示函数通过事前分析给岀算法计算时间（频率计数）的一个函数表示形式，一般记为与输入规模n有关的函数形式：f（n）注：最高次项与函数整体的关系■空间特性分析（与时间特性的分析类似，略）2）事后测试■U的：运行程序，确定程序实际耗费的吋间与空间，验证先前的分析结论——包括正确性、执行性能等，比较、优化所设计的算法。■分析乎段：作时、空性能分布图。5.计算时间的渐近表示记：算法的计算时间为f（n）数量级限界函数为g（n）其中，■n是输入或输出规模的某种测度。■f(n)表示算法的“实际”执行吋间一与机器及语言有关

8、。-g(n)是形式简单的函数，如nm,logo,2n,n!等。是事前分析屮通过对计算时间或频率计数统计分析所得的与机器及语言无关的函数。以下给出算法执行吋间：上界(())、下界(Q)、i°平均i土()的定义。渐进意义下的记号：0,Q,定义1.1如果存在两个止常数c和N(),对于所有的N3N。,有『(MlWCIg(N)l,贝I」记作