第一章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)的连续整数检测算法第一步：将minm,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为常数nO(n)100n+5O(n)n(n-1)/2O(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)elemt.keys-elemj.key)t=j；/*t中存放关键码最小记录的下标*/s-elemts-elemi；/*关键码最小的记录与第i个记录交换*/,各种排序算法比较,三、冒泡排序(BubbleSort)1）基本思想：两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止2）排序过程：设想被排序的数组R1.N垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上“漂浮”，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。示例：49131313131313133849272727272727653849383838383897653849494949497697654949494949137697656565656527277697767676764949497697979797,各种排序算法比较,冒泡排序算法实践：voidsb_sort(inte,intn)intj,h,t，i;i=1；for(h=n-i;h0;i+)for(j=0;jh;j+)if(ejlowhigh作快排序*/if(lowhigh)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）基本思想：堆排序是一树形选择排序，在排序过程中，将R1.N看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。2）堆的定义:N个元素的序列K1,K2,K3,.,Kn.称为堆，当且仅当该序列满足特性：KiK2iKiK2i+1(1IN/2)堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。,各种排序算法比较,3）排序过程：堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。,各种排序算法比较,示例：对关键字序列42，13，91，23，24，16，05，88建堆堆排序voidsift(e,n,s)inte;intn;ints;intt,k,j;t=es;k=s;j=2*k+1;while(j=1;k-)t=e0;e0=ek;ek=t;sift(e,k,0);,各种排序算法比较,几种排序算法的比较和选择:1）选取排序方法需要考虑的因素：(1)待排序的元素数目n；(2)元素本身信息量的大小；(3)关键字的结构及其分布情况；(4)语言工具的条件，辅助空间的大小等。2）小结：(1)若n较小(n=50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。(2)若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。,各种排序算法比较,(3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序法中被认为是最好的方法。(4)在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于“比较”的排序算法，至少需要O(nlog2n)的时间。(5)当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。,各种排序算法比较,比较一下上面谈到的各种内部排序方法：首先，