●●●●● ●●●● ●●0 ●●● ●●●● 5.课程关系 数据结构 程序设计语言:结构化设计 数学基础 非数值计算领域的基本知识 2021/2/20
2021/2/20 5. 课程关系 数据结构 程序设计语言：结构化设计 数学基础 非数值计算领域的基本知识
●●●●● ●●●● 1.2分析算法 ●●0 ●●● ●●●● 分析算法的目的 在于:通过对算法的分析,在把算法变成程序实际运行前, 就知道为完成一项任务所设计的算法的好坏,从而运行好的算 法,改进差的算法,避免无益的人力和物力浪费 算法分析是计算机领域的“古老”而“前沿”的课题。 2021/2/20
2021/2/20 1.2 分析算法 1. 分析算法的目的 在于：通过对算法的分析，在把算法变成程序实际运行前， 就知道为完成一项任务所设计的算法的好坏，从而运行好的算 法，改进差的算法，避免无益的人力和物力浪费。 算法分析是计算机领域的“古老”而“前沿”的课题
●●●●● ●●●● ●●0 2.重要的假设和约定 ●●● ●●●● 1)计算机模型的假设 计算机形式理论模型: Turing机模型 通用计算机模型: 顺序计算机 有足够的“内存” 能在固定的时间内存取数据单元 2021/2/20
2021/2/20 2. 重要的假设和约定 1）计算机模型的假设 ⚫ 计算机形式理论模型：Turing机模型 ⚫ 通用计算机模型： ➢ 顺序计算机 ➢ 有足够的“内存” ➢ 能在固定的时间内存取数据单元
●●●●● ●●●● 2)计算的约定 ●●0 ●●● 算法的执行时间=f ●●●● 其中,f是算法中用到的某种运算的次数——称为该运算的“频率计数” t是该运算执行一次所用的时间—与程序语言和硬件有关 确定:使用何种运算及其执行时间。 ●从运算的“时间特性”上将运算的分类: 时间囿界于常数的运算 基本算术运算,如整数、浮点数的加、减、乘、除 字符运算、赋值运算、过程调用等 特点:尽管每种运算的执行时间不同,但一般只花 固定量的时间(单位时间)就可完成 2021/2/20
2021/2/20 2）计算的约定 算法的执行时间=∑fi *ti 其中，f i是算法中用到的某种运算i的次数——称为该运算的“频率计数” t i是该运算执行一次所用的时间 —— 与程序语言和硬件有关 确定：使用何种运算及其执行时间。 ⚫ 从运算的“时间特性”上将运算的分类： ➢ 时间囿界于常数的运算： ·基本算术运算，如整数、浮点数的加、减、乘、除 ·字符运算、赋值运算、过程调用等 特点：尽管每种运算的执行时间不同，但一般只花一个 固定量的时间（单位时间）就可完成
●●●●● ●●●● ●●0 2)计算的约定(续) ●●● ●●●● >其他运算: 字符串操作:与字符串中字符的数量成正比 ·记录操作:与记录的属性数、属性类型等有关 特点:运算时间无定量 如何分析非时间囿界于常数的运算:分解成若干时间囿 界于常数的运算 tn: tstring Length( String )* tchar 2021/2/20
2021/2/20 2）计算的约定（续） ➢ 其他运算： ·字符串操作：与字符串中字符的数量成正比 ·记录操作：与记录的属性数、属性类型等有关 特点：运算时间无定量。 如何分析非时间囿界于常数的运算：分解成若干时间囿 界于常数的运算。 如：tstring = Length（String）* tchar