,是其他算法的基础。 这类算法在程序中应用非常普遍,如:累加求 和、累乘求积、求最大和最小值等。
Delphi程序设计大学教程 Delphi程序
设计大学教程
5.1.2
2.
常用算法
排序算法
排序算法根据数据的值对它们进行排列。排序 是为了把不规则的信息进行整理,以提高查找 信息的效率。 常用的排序方法包括:选择排序、冒泡排序、 插入排序等。这三种方法是程序设计中使用的 快速排序的基础。
Delphi程序设计大学教程
Delphi程序设计大学教程
5.1.2
3.
常用算法
查找算法
查找是一种在列表(list)中确定目标所在位置 的算法。在一个列表中,查找意味给定一个值, 并在包含该值的列表中找到该值的第一个元素 的位置(索引)。 对于
列表有两种基本的查找方法:顺序查找和 折半查找。顺序查找可以在任何列表中查找, 折半查找则需要列表是有序的。
Delphi程序设计大学教程 Delphi程序设计大学教程
5.1.2
4.
常用算法
迭代和递归算法
迭代和递归是用于编写解决问题的算法的两种 途径。一种使用迭代,另一种使用递归。
迭代 “迭”是屡次和反复的意思,“代”是替换 的意思,合起来,“迭代”就是反复替换的意思, 也就是使用一个中间变量保存中间结果,不断反复 计算求解最终值。 递归 递归是一个算法自我调用的过程,用递归调 用的算法就是递归算法。
Delphi程序设计大学教程 Delphi程序设计大学教程
5.1.3
算法复杂性分析*
算法的复杂性是指:在执行时,算法所需要 计算机资源的量。需要的时间资源的量称作 时间复杂性,需要的空间(即存储器)资源 的量称作空间复杂性。这个量应该集中反映 算法中所采用的方法的效率,而从运行该算 法的实际计算机中抽象出来。
Delphi程序设计大学教程 Delphi程序设计大学教程
5.1.3
算法复杂性分析*
1. 时间复杂性
时间复杂性描述了算法在
计算机上执行时,所占用的计 算机时间资源的情况。它是一种抽象的描述方式,并不 是指与算法实现效率有关的算法执行时间,而是指理论 上与
问题规模、算法输入及算法本身相关的某些操作次 数的总和,通常记为T(n)。问题规模逐渐增大后时间复 杂度的极限形式称为渐进时间复杂性(Asymptotic Time Complexity),渐进时间复杂性确定了算法所能 解决问题的规模,通常用来分析随着问题规模的加大, 算法对时间需求的增长速度。
Delphi程序设计大学教程 Delphi程序设计大学教程
5.1.3
算法复杂性分析*
2. Fibonacci问题
Fibonacci数列是一个无穷数列,具体构成为: 0,1,2,3,5,8,13,21,34,55,… 它可以定义为: F(0) = F(1) = 1 F(i) = F(i-1) + F(i-2) i>1 即后面的每个Fibonacci值是前两个Fibonacci值之和。
现在的任务是如何求得Fibonacci数列中的第n个 数。下面介绍两种求解
方案:递推和递归。
Delphi程序设计大学教程 Delphi程序设计大学教程
5.1.3
算法复杂性分析*
(1) 递推与迭代 递推与迭代都是重要的数学方法,它们在计算机中的应 用也非常广泛。递推关系是一种随着变量的递增产生连 锁反映的关系。所谓递推法,就是通过迭代运算对问题 进行求解的方法。 递推算法的一般模式为:
v = v0 当条件p(v)成立,则重复执行 v = f(v) 先求得初值 v = v0,然后将每次计算的值v 代入递推公式 v = f(v),求得新的v,直到条 件p(v)不成立为止。
Delphi程序设计大学教程 Delphi程序设计大学教程
5.1.3
(2)
算法复杂性分析*
递归
递归在数学和计算机中经常遇到。利用递归方法可 以用有限的语句来定义无限集合,但在递归定义中 至少有一条是非递归的,即初始定义,否则就会产 生逻辑性错误。
Delphi程序设计大学教程 Delphi程序设计大学教程
5.2 集合
5.2.1 关系运算 5.2.2 增删元素 5.2.3 交集运算
Delphi程序设计大学教程 Delphi程序设计大学教程
5.2
集合
集合类型是一群相同类型