计算机算法基础.ppt

计算机算法基础
*
第1页，此课件共67页哦
序
专业基础课程：
数据结构、计算机语言
操作系统、编译
如何编写计算机程序：
数据结构+算法 = 程序
算法：计算机软件的“灵魂”
算法析算法
1. 分析算法的目的
在于：通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。
算法分析是计算机领域的“古老”而“前沿”的课题。
*
第12页，此课件共67页哦
2. 重要的假设和约定
1）计算机模型的假设
计算机形式理论模型： Turing机模型
通用计算机模型：
顺序计算机
有足够的“内存”
能在固定的时间内存取数据单元
*
第13页，此课件共67页哦
2）计算的约定
算法的执行时间=∑fi*ti
其中，fi是算法中用到的某种运算i的次数——称为该运算的“频率计数”
ti是该运算执行一次所用的时间 —— 与程序语言和硬件有关

确定：使用何种运算及其执行时间。
从运算的“时间特性”上将运算的分类：
时间囿界于常数的运算：
·基本算术运算，如整数、浮点数的加、减、乘、除
·字符运算、赋值运算、过程调用等
特点：尽管每种运算的执行时间不同，但一般只花一个
固定量的时间（单位时间）就可完成。
*
第14页，此课件共67页哦
2）计算的约定（续）
其他运算：
·字符串操作：与字符串中字符的数量成正比
·记录操作：与记录的属性数、属性类型等有关
特点：运算时间无定量。
如何分析非时间囿界于常数的运算：分解成若干时间囿界于常数的运算。

如：tstring = Length（String）* tchar
*
第15页，此课件共67页哦
3）工作数据集的选择
编制能够反映算法在最好、平均、最坏情况下工作的数据配置。然后使用这些数据配置运行算法，以了解算法的性能。
编制测试数据是程序测试与算法分析中的关键技术之一。
·作为算法分析的数据集：反映算法的典型特征
·作为程序正确性及性能测试的数据集：测试程序的对错，反映对性能指标产生影响的方面,如边界值
*
第16页，此课件共67页哦
3. 如何进行算法分析？
对算法进行全面分析，可分两个阶段进行：
事前分析：求算法的一个时间/空间限界函数，即通过对算
法的“理论”分析，得出关于算法时间和空间特性
的特征函数（Ο、Ω）——与计算机物理软硬
件没有直接关系。
事后测试：将算法编制成程序后实际放到计算机上运行，
收集其执行时间和空间占用等统计资料，进行
分析判断——直接与物理实现有关。
*
第17页，此课件共67页哦
1）事前分析
目的：试图得出关于算法特性的一种形式描
述，以“理论上”衡量算法的“好坏”。
如何给出反映算法特性的描述？
统计算法中各种运算的执行情况，包括：
引用了哪些运算
每种运算被执行的次数
该种运算执行一次所花费的时间等。
算法的执行时间=∑fi*ti
*
第18页，此课件共67页哦
频率计数
频率计数：算法中语句或运算的执行次数。
例：
x←x+y for i ←1 to n do for i ←1 to n do
x ← x + y for j ←1 to n do
repeat x ← x +y