计算机算法基础第一章(与“算法”有关的共103张).pptx

计算机算法基础第一章;有两种思想,像珠宝商放在天鹅绒上的宝石一样熠熠生辉.一个是微积分，另一个就是算法.微积分以及在微积分基础上建立起来的数学分析体系造就了现代科学,而算法造就了现代世界.

——DavidBerlinski;算法的研究内容;算法的应用;章节安排;预备知识;第一章导引与基本数据结构;2.算法的五个重要特性

确定性、能行性、输入、输出、有穷性;2）能行性

算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成。

例：整数的算术运算是“能行”的

实数的算术运算是“不能行”的

;3）输入

每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合——定义域（或值域）

;5）有穷性

一个算法总是在执行了有穷步的运算之后终止。

计算过程：只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。

准确理解算法和计算过程的区别：

不能终止的计算过程：操作系统

算法是“可以终止的计算过程”

算法的时效性：只能把在相当有穷步内终止的算法投

入到计算机上运行;3.我们的主要任务

算法学习将涉及5个方面的内容：

1）设计算法：创造性的活动

2）表示算法：思想的表示形式

3）确认算法：证明算法的正确性

程序的证明

4）分析算法：算法时空特性分析

5）测试程序：调试和作出时空分布图

本课程集中于学习算法的设计与分析。通过学习，掌握计算机算法设计和分析基本策略与方法，为设计更复杂、更有效的算法奠定基础;;;1.2分析算法;2.重要的假设和约定

1）计算机模型的假设

Turing机模型：计算机形式理论模型

通用计算机模型：

单处理器

有足够的“内存”

能在固定的时间内存取数据单元

;2）计算的约定

确定使用什么样的运算及其执行时间。

从计算时间上，运算的分类：

时间囿界于常数的运算：尽管每种运算的执行时间不同，但一般只花一个固定量的时间（单位时间）就可完成。

·基本算术运算，如整数、浮点数的加、减、乘、除

·字符运算

·赋值运算

·过程调用等;2）计算的约定（续）;3）工作数据集的选择

编制能够反映算法在最好、平均、最坏情况下工作的数据配置。然后使用这些数据配置运行算法，以了解算法的性能。

测试数据集的生成

作为算法分析的数据集：典型特征

作为程序性能测试的数据集：对执行指标产生影响的性质;3.如何进行算法分析？

对算法进行全面分析，可分两个阶段进行：

事前分析：就算法本身，通过对其执行性能的理论分析，

得出关于算法特性——时间和空间的一个特征

函数（Ο、Ω）——与计算机物理软硬件没有

直接关系。

事后测试：将算法编制成程序后实际放到计算机上运行，

收集其执行时间和空间占用等统计资料，进行

分析判断——直接与物理实现有关。;1）事前分析

目的：试图得出关于算法执行特性的一种形式描

述，以“理论上”衡量算法的“好坏”。

如何给出反映算法执行特性的描述？

最直接方法：统计算法中各种运算的执行情况，包括：

运用了哪些运算

每种运算被执行的次数

该种运算执行一次所花费的时间等。

算法的执行时间=∑Fi*ti;频率计数

例：

x←x+yfori←1tondofori←1tondo

x←x+yforj←1tondo