文档介绍：算法的概念
利用计算机求解问题的一般过程
(1)问题分析阶段
(2)数据结构设计阶段
(3)算法设计阶段
(4)编码与调试阶段
程序=数据结构+算法
算法(Algorithm):对特定问题求解步骤的一种描述,是指令的有限序列。
算法的五个重要特性:
1) 有穷性
2)确定性
3)可行性
4)0到多个输入
5)1到多个输出
算法分类:
(1)数值运算算法
(2)非数值运算算法
算法设计的要求
算法与程序的关系
算法是供人阅读的
程序是让机器执行的
算法用计算机语言实现时就是程序
程序不具有算法的有穷性
算法应达到的目标
正确性
可读性
健壮性
效率与低存贮量
算法设计的特点
解决同一问题可有不同的方法步骤
算法有优劣,看时间和空间占用情况
不是所有算法都能在计算机上实现
首先,算法应当满足以特定的“规格说明”方式给出的需求。
其次,对算法是否“正确”的理解可以有以下四个层次:
;
;
、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果;
通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。
;
2. 可读性
算法主要是为了人的阅读与交流,
其次才是为计算机执行,因此算法应该易于人的理解;另一方面,晦涩难读的程序易于隐藏较多错误而难以调试。
当输入的数据非法时,算法应当恰当地作出反映或进行相应处理,而不是产生莫名奇妙的输出结果。并且,处理出错的方法不应是中断程序的执行,而应是返回一个表示错误或错误性质的值,以便在更高的抽象层次上进行处理。
通常,效率指的是算法执行时间;
存储量指的是算法执行过程中所需的
最大存储空间,两者都与问题的规模
有关。
算法效率的度量
1) 事后统计法(需先运行程序、统计有赖于计算机软硬环境)
2)事前分析估算法
运行时间取决于如下因素:
算法策略、问题规模、程序语言、编译程序、机器速度
算法的时间复杂度:基本操作(原操作)重复执行的次数。
它是问题规模n的某个函数f(n):
T(n) = O(f(n))(表明随n 的增大,算法执行时间的增长率和f(n)的增长率相同,称做算法的渐进时间复杂度)
语句频度:该语句重复执行的次数
如何估算
算法的时间复杂度?
算法= 控制结构+ 原操作
(固有数据类型的操作)
算法的执行时间=
原操作(i)的执行次数×原操作(i)的执行时间
算法的执行时间
与
原操作执行次数之和成正比