第一章GIS算法.ppt

地理信息系统算法 第一章算法设计和分析 第一节概述 第二节算法设计原则 第三节算法复杂性的度量 第四节最优算法 第一节概述 一 算法的概念 算法是一系列解决问题的清晰指令 也就是说 能够对一定规范的输入 在有限时间内获得所要求的输出 二 算法特性 有穷性 确定性 可行性 有输入 有输出 1 有穷性 对于任意一组合法输入值 在执行有穷步骤之后一定能结束 即 算法中的每个步骤都能在有限时间内完成 2 确定性 对于每种情况下所应执行的操作 在算法中都有确切的规定 使算法的执行者或阅读者都能明确其含义及如何执行 并且在任何条件下 算法都只有一条执行路径 3 可行性 算法中的所有操作都必须足够基本 都可以通过已经实现的基本操作运算有限次实现之 4 有输入 作为算法加工对象的量值 通常体现为算法中的一组变量 有些输入量需要在算法执行过程中输入 而有的算法表面上可以没有输入 实际上已被嵌入算法之中 5 有输出 它是一组与 输入 有确定关系的量值 是算法进行信息加工后得到的结果 这种确定关系即为算法的功能 第一节概述 三 算法的几个要点 1 算法的每一个步骤都必须清晰 明确 2 算法所处理的输入的值域必须仔细定义 3 同样的一个算法可以用几种不同的形式来描述 4 可能存在几种解决相同问题的算法 5 针对同一个问题的算法可能会基于完全不同的解题思路 而且解题的速度也会有明显区别 第一节概述 Example求两个正整数m n的最大公约数gcd m n 1 同一个算法有不同的表达方式 1 第一节概述 gcd m n 的欧几里得算法第一步 如果n 0 返回m的值作为结果 结束 否则进入第二步第二步 用n去除m 将余数赋给r 第三步 将n的值赋给m 将r的值赋给n 回第一步 2 算法Euclid m n 使用欧几里得算法计算gcd m n 输入 两个不全为0的非负整数m n 输出 m n的最大公约数Whilen 0dormmodnmnnrReturnm 第一节概述 2 同一个问题有不同的解决方法 1 gcd m n 的连续整数检测算法第一步 将min m n 的值赋给t 第二步 m除以t 如果余数为0 则进入第三步 否则 进入第四步 第三步 n除以t 如果余数为0 则返回t值作为结果 否则 进入第四步 第四步 把t的值减1 返回第二步 2 gcd m n 的中学计算算法第一步 找到m的所有质因数 第二步 找到n的所有质因数第三步 从第一步和第二步中求得的质因数分解式找出所有的公因数 第四步 将第三步中找的质因数相乘 其结果作为给定数字的最大公因数 第一节概述 算法问题求解的过程 第一节概述 理解问题 决定 计算方法 精确和近似的解法 设计算法 正确性证明 分析算法 根据算法写代码 设计算法前做的第一件事情 仔细阅读问题的描述提出疑问理解问题 手工处理一些实例考虑特殊情况确定输入抽象出问题 用数学表达式描述选择精确解和近似解 某些重要的问题无法求得精确解某些问题利用精确解速度慢 无法接受 第一节概述 算法设计技术 使用算法解题的一般性方法 用于解决计算领域的多种问题 详细表述算法的方法 自然语言 用我们日常生活中的自然语言 可以是中文形式 也可以是英文形式 也可以描述算法 伪代码 我们可以用数学语言或约定的符号语言来描述算法 流程图 一个算法可以用流程图的方式来描述 输入输出 判断 处理分别用不同的框图表示 用箭头表示流程的流向 这是一种描述算法的较好方法 目前在一些高级语言程序设计中仍然采用 也有其他的图形辅助工具 第一节概述 证明算法的正确性 证明对于每一个合法的输入 该算法都会在有限的时间内输出一个满足要求的结果 一般方法 数学归纳法证明算法的正确性与不正确哪一个更容易 分析算法 算法有两种效率 时间效率和空间效率 算法的另外两个特性 简单性和一般性 第一节概述 为算法写代码 用计算机程序实现算法 在把算法转变为程序的过程中 可能会发生错误或者效率非常低 作为一种规律 一个好的算法是反复努力和重新修正的结果算法是一个最优性问题 对于给定的问题需要花费多少力气 资源 是不是每个问题都能够用算法的方法来解决 发明或发现算法是一个非常有创造性和非常值得付出的过程 第一节概述 算法和程序的关系 1 算法着重体现思路和方法 程序着重体现计算机的实现 2 程序不一定满足有穷性 死循环 另外 程序中的指令必须是机器可执行的 算法中的指令无此限制 3 一个算法若用计算机语言来书写 它就可以是一个程序 第一节概述 第二节算法设计原则 1 正确性 是指对于一个问题 之所以将其放在第一位是因为如果一个算法自身有缺陷 或者不适合于问题的求解 那么该算法将不会解决问题 2 确定性 是指算法的每个步骤必须含义明确 对每种可能的情况 算法都能给出确定的操作 即采用同一种算法 在同样的条件下无论计算多少次 始终能够得到确定的结果 3 清晰性 一个良好的算法必须思路清晰 结构合理 算法的设计要模块化 模块化的目的是使算法结构清晰 容易阅读 容易理解 容易测试 容易修改 第三节算法复杂性的度量 算法分析 是对一个算法需要多少计算时间和存储空间作定量的分析 即时间特性 时间复杂度T n 和空间特性 空间复杂度S n 一个特定算法的 运行工作量 的大小 只依赖于问题的规模 通常用整数量n表示 或者说 它是问题规模的函数 时间复杂度 假如 随着问题规模n的增长 算法执行时间的增长率和f n 的增长率相同 则可记作 T n O f n 称T n 为算法的 渐近 时间复杂度 第三节算法复杂性的度量 如何估算算法的时间复杂度 算法 控制结构 顺序 分支和循环三种 原操作 固有数据类型的操作 算法的执行时间 原操作 i 的执行次数 原操作 i 的执行时间算法的执行时间与原操作执行次数之和成正比从算法中选取一种对于所研究的问题来说是基本操作的原操作 以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则 第三节算法复杂性的度量 算法效率的主要指标是基本操作次数的增长次数 增长次数 小规模输入在运行时间上的差别不足以将高效的算法和低效的算法区分开来 第三节算法复杂性的度量 为了对这些增长次数进行比较和归类 计算机科学家们使用了3种符号 O 读 O 上界 读 omega 下界 读 theta 相等1 符号O定义1对于足够大的n t n 的上界由g n 的常数倍来确定 即 记为t n O g n t n cg n c为常数n O n 100n 5 O n n n 1 2 O n 第三节算法复杂性的度量 2 符号 定义 对于足够大的n t n 的下界由g n 的常数倍来确定 即 记为t n g n t n cg n c为常数n n n n 1 n 4n 5 n 第三节算法复杂性的度量 符号 定义 对于足够大的n t n 的上界和下界由g n 的常数倍来确定 即 c1g n t n c2g n c1 c2为常数记为t n g n n 3n 2 n n n 1 2 n 4n 5 n 第三节算法复杂性的度量 渐进符号的有用特性 定理 如果t1 n O g1 n 并且t2 n O g2 n 则t1 n t2 n O max g1 n g2 n 对于符号 和 该定理也成立 该定理表明 当算法由两个连续执行部分组成时 该算法的整体效率由具有较大增长次数的那部分所决定 利用极限比较增长次数前两种情况意味着t n O g n 后两种情况意味着t n g n 第二种情况意味着t n g n 第三节算法复杂性的度量 基本的效率类型指数时间算法一般有 O O n O 常量 1 对数 logn 线性 n 平方 n 立方 n 指数 2n 阶乘 n 其中有六种多项式时间算法最为常见 其关系为 O 1 O logn O n O nlogn O n2 O n3 第三节算法复杂性的度量 voidmult inta intb int 基本操作 乘法操作时间复杂度 O n 例一两个矩阵相乘 第三节算法复杂性的度量 voidselect sort intif j i a j a i 基本操作 比较 数据元素 操作时间复杂度 O n 例二选择排序 空间复杂度 算法在运行过程中临时占用的存储空间的大小被定义为算法的空间复杂性 空间复杂性包括程序中的变量 过程或函数中的局部变量等所占用的存储空间以及系统为了实现递归所使用的堆栈两部分 算法的空间复杂性一般也以数量级的形式给出 S n O g n 表示随着问题规模n的增大 算法运行所需存储量的增长率与g n 的增长率相同 第三节算法复杂性的度量 第四节最优算法 算法的最优 最差和平均效率1 最差效率是指在输入规模为n时 算法在最坏情况下的效率 2 最优效率是指在输入规模为n时 算法在最优情况下的效率 3 平均效率是指在 典型 或 随机 输入的情况下 算法具有的行为 效率 4 摊销效率是指对于同样的数据结构执行多次操作 然后分摊到每一次上 第四节最优算法 算法优化的几种常用方法 1 空间换时间算法中的时间和空间往往是矛盾的 时间复杂性和空间复杂性在一定条件下也是可以相互转化的 有时候为了提高程序运行的速度 在算法的空间要求不苛刻的前提下 设计算法时可考虑充分利用有限的剩余空间来存储程序中反复要计算的数据 这就是 用空间换时间 策略 是优化程序的一种常用方法 相应的 在空间要求十分苛刻时 程序所能支配的自由空间不够用时 也可以以牺牲时间为代价来换取空间 由于当今计算机硬件技术发展很快 程序所能支配的自由空间一般比较充分 这一方法在程序设计中不常用到 2 尽可能利用前面已有的结论 比如递推法 构造法和动态规划就是这一策略的典型应用 利用以前计算的结果在后面的计算中不需要重复 第四节最优算法 3 寻找问题的本质特征 以减少重复操作 算法的复杂度分析不仅可以对算法的好坏作出客观的评估 同时对算法设计本身也有着指导性作用 因为在解决实际问题时 算法设计者在判断所想出的算法是否可行时 通过对算法作事先评估能够大致得知这个算法的优劣 进而作出决定是否采纳该算法 这样就能避免把大量的精力投入到低效算法的实现中去 特别是现在举行的各级信息学奥林匹克竞赛对程序的运行时间都有着相当严格的限制 掌握好算法复杂度的大致评估方法就显得犹为重要 常用算法分析 递归的定义 一个过程 或函数 直接或间接调用自己本身 这种过程 或函数 叫递归过程 或函数 有直接调用和间接调用两种 设计递归算法 主要有两步 1 确定递归公式 2 确定边界 终了 条件 要注意学会把具体问题分解为几个子问题 如果你分解的这些子问题的形式和算法与原问题相似 那么 你的递归算法就能很快完成 能采用递归描述的算法通常有这样的特征 为求解规模为N的问题 设法将它分解成规模较小的问题 然后从这些小问题的解方便地构造出大问题的解 并且这些规模较小的问题也能采用同样的分解和综合方法 分解成规模更小的问题 并从这些更小问题的解构造出规模较大问题的解 特别地 当规模N 1时 能直接得解 为了描述问题的某一状态 必须用到它的上一状态 而描述上一状态 又必须用到它的上一状态 这种用自已来定义自己的方法 称为递归定义 常用算法分析 例如 定义函数f n 为 f n n f n 1 n 0 f n 1 n 0 则当0时 须用f n 1 来定义f n 用f n 1 1 来定义f n 1 当n 0时 f n 1 由上例我们可看出 递归定义有两个要素 1 递归边界条件 也就是所描述问题的最简单情况 它本身不再使用递归的定义 如上例 当n 0时 f n 1 不使用f n 1 来定义 2 递归定义 使问题向边界条件转化的规则 递归定义必须能使问题越来越简单 如上例 f n 由f n 1 定义 越来越靠近f 0 也即边界条件 最简单的情况是f 0 1 递归算法的效率往往很低 费时和费内存空间 但是递归也有其长处 它能使一个蕴含递归关系且结构复杂的程序简化精炼 增加可读性 特别是在难于找到从边界到解的全过程的情况下 如果把问题推进一步简化而其结果仍维持原问题的关系 则采用递归算法编程比较合适 各种排序算法比较 一 插入排序 InsertionSort 1 基本思想 每次将一个待排序的数据元素 插入到前面已经排好序的数列中的适当位置 使数列依然有序 直到待排序数据元素全部插入完为止 2 排序过程 示例 初始关键字 49 38659776132749J 2 38 3849 659776132749J 3 65 384965 9776132749J 4 97 38496597 76132749J 5 76 3849657697 132749J 6 13 133849657697 2749J 7 27 13273849657697 49J 8 49 1327384949657697 各种排序算法比较 直接插入排序 voidsi sort inte intn inti j t for i 0 i 0 各种排序算法比较 二 选择排序1 基本思想 每一趟从待排序的数据元素中选出最小 或最大 的一个元素 顺序放在已排好序的数列的最后 直到全部待排序的数据元素排完 2 排序过程 示例 初始关键字 4938659776132749 第一趟排序后13 38659776492749 第二趟排序后1327 659776493849 第三趟排序后132738 9776496549 第四趟排序后13273849 49976576 第五趟排序后1327384949 979776 第六趟排序后132738494976 7697 第七趟排序后13273849497676 97 最后排序结果1327384949767697 各种排序算法比较 选择排序主要是每一趟从待排序列中选取一个关键码最小的记录 也即第一趟从n个记录中选取关键码最小的记录 第二趟从剩下的n 1个记录中选取关键码最小的记录 直到整个序列的记录选完 这样 由选取记录的顺序 便得到按关键码有序的序列 操作方法 第一趟 从n个记录中找出关键码最小的记录与第一个记录交换 第二趟 从第二个记录开始的n 1个记录中再选出关键码最小的记录与第二个记录交换 如此 第i趟 则从第i个记录开始的n i 1个记录中选出关键码最小的记录与第i个记录交换 直到整个序列按关键码有序 各种排序算法比较 算法 voidSelectSort S TBL s for i 1 ilength i 作length 1趟选取 for j i 1 t i jlength j 在i开始的length n 1个记录中选关键码最小的记录 if s elem t key s elem j key t j t中存放关键码最小记录的下标 s elem t s elem i 关键码最小的记录与第i个记录交换 各种排序算法比较 三 冒泡排序 BubbleSort 1 基本思想 两两比较待排序数据元素的大小 发现两个数据元素的次序相反时即进行交换 直到没有反序的数据元素为止2 排序过程 设想被排序的数组R 1 N 垂直竖立 将每个数据元素看作有重量的气泡 根据轻气泡不能在重气泡之下的原则 从下往上扫描数组R 凡扫描到违反本原则的轻气泡 就使其向上 漂浮 如此反复进行 直至最后任何两个气泡都是轻者在上 重者在下为止 示例 49131313131313133849272727272727653849383838383897653849494949497697654949494949137697656565656527277697767676764949497697979797 各种排序算法比较 冒泡排序算法实践 voidsb sort inte intn intj h t i i 1 for h n i h 0 i for j 0 j h j if e j e j 1 t e j e j e j 1 e j 1 t 各种排序算法比较 冒泡排序 BubbleSort 算法分析 先来看看待排序列一趟冒泡的过程 设1r i 1 key时 r 0 r i r i r i 1 r i 1 r 0 将r i 与r i 1 交换 i i 1 调整对下两个记录进行两两比较 转 冒泡排序方法 对n个记录的表 第一趟冒泡得到一个关键码最大的记录r n 第二趟冒泡对n 1个记录的表 再得到一个关键码最大的记录r n 1 如此重复 直到n个记录按关键码有序的表 各种排序算法比较 四 快速排序 QuickSort 1 基本思想 在当前无序区R 1 H 中任取一个数据元素作为比较的 基准 不妨记为X 用此基准将当前无序区划分为左右两个较小的无序区 R 1 I 1 和R I 1 H 且左边的无序子区中数据元素均小于等于基准元素 右边的无序子区中数据元素均大于等于基准元素 而基准X则位于最终排序的位置上 即R 1 I 1 X Key R I 1 H 1 I H 当R 1 I 1 和R I 1 H 均非空时 分别对它们进行上述的划分过程 直至所有无序子区中的数据元素均已排序为止 各种排序算法比较 2 排序过程 示例 初始关键字 4938659776132749 第一次交换后 2738659776134949 第二次交换后 2738499776136549 J向左扫描 位置不变 第三次交换后 2738139776496549 I向右扫描 位置不变 第四次交换后 2738134976976549 J向左扫描 2738134976976549 各种排序算法比较 一次划分过程 初始关键字 4938659776132749 一趟排序之后 273813 49 76976549 二趟排序之后 13 27 38 49 4965 76 97 三趟排序之后1327384949 65 7697最后的排序结果1327384949657697快速排序是通过比较关键码 交换记录 以某个记录为界 该记录称为支点 将待排序列分成两部分 其中 一部分所有记录的关键码大于等于支点记录的关键码 另一部分所有记录的关键码小于支点记录的关键码 我们将待排序列按关键码以支点记录分成两部分的过程 称为一次划分 对各部分不断划分 直到整个序列按关键码有序 各种排序算法比较 算法 voidQSort S TBL tbl intlow inthigh 递归形式的快排序 对顺序表tbl中的子序列tbl low high 作快排序 if low high pivotloc partition tbl low high 将表一分为二 QSort tbl low pivotloc 1 对低子表递归排序 QSort tbl pivotloc 1 high 对高子表递归排序 各种排序算法比较 效率分析 空间效率 快速排序是递归的 每层递归调用时的指针和参数均要用栈来存放 递归调用层次数与上述二叉树的深度一致 因而 存储开销在理想情况下为O log2n 即树的高度 在最坏情况下 即二叉树是一个单链 为O n 时间效率 在n个记录的待排序列中 一次划分需要约n次关键码比较 时效为O n 若设T n 为对n个记录的待排序列进行快速排序所需时间 理想情况下 每次划分 正好将分成两个等长的子序列 则T n cn 2T n 2 c是一个常数 cn 2 cn 2 2T n 4 2cn 4T n 4 2cn 4 cn 4 T n 8 3cn 8T n 8 cnlog2n nT 1 O nlog2n 各种排序算法比较 最坏情况下 即每次划分 只得到一个子序列 时效O n 快速排序是通常被认为在同数量级 O nlog2n 的排序方法中平均性能最好的 但若初始序列按关键码有序或基本有序时 快排序反而蜕化为冒泡排序 为改进之 通常以 三者取中法 来选取支点记录 即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录 快速排序是一个不稳定的排序方法 各种排序算法比较 五 堆排序 HeapSort 1 基本思想 堆排序是一树形选择排序 在排序过程中 将R 1 N 看成是一颗完全二叉树的顺序存储结构 利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素 2 堆的定义 N个元素的序列K1 K2 K3 Kn 称为堆 当且仅当该序列满足特性 Ki K2iKi K2i 1 1 I N 2 堆实质上是满足如下性质的完全二叉树 树中任一非叶子结点的关键字均大于等于其孩子结点的关键字 例如序列10 15 56 25 30 70就是一个堆 它对应的完全二叉树如上图所示 这种堆中根结点 称为堆顶 的关键字最小 我们把它称为小根堆 反之 若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字 则称之为大根堆 各种排序算法比较 3 排序过程 堆排序正是利用小根堆 或大根堆 来选取当前无序区中关键字小 或最大 的记录实现排序的 我们不妨利用大根堆来排序 每一趟排序的基本操作是 将当前无序区调整为一个大根堆 选取关键字最大的堆顶记录 将它和无序区中的最后一个记录交换 这样 正好和直接选择排序相反 有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区 各种排序算法比较 示例 对关键字序列42 13 91 23 24 16 05 88建堆堆排序voidsift e n s inte