二叉排序树用于动态查找.ppt

时间空间复杂度 算法效率的度量 算法执行时间需要通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法： 事后统计的方法 可以利用计算机的内部计时功能，先把程序编写好运行一下进行计时。不过这种方法有两个缺陷： 一是必须先编制好程序并运行； 二是所得出的时间统计量依赖于计算机的软硬件等环境因素，有时容易掩盖算法本身的优劣性。 事先分析估算的方法 A）依据的算法选用何种策略； B）问题的规模。例如求100以内还是10000以内的素数； C）书写程序的语言。对于同一个算法，实现语言的级别越高，执行效率就越低； D）编译程序产生的机器代码的质量； E）机器执行指令的速度。 显然，同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行时，效率均不相同。 这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。 一个算法是由控制结构（顺序、分支和循环）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。 为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本运算的原操作，以该基本操作重复执行的次数作为算法的时间量度。 时间复杂度 时间复杂度：  一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。  例如在如下所示的两个N*N矩阵相乘的算法中,“乘法”运算时“矩阵相乘问题”的基本操作。 for i:=1 to n do for j:=1 to n do begin c[i,j]:=0; for k:=1 to n do c[i,j]:=c[i,j]+a[i,k]*b[k,j] end; 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f (n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。  整个算法的执行时间与该基本操作（乘法）重复执行的次数N3成正比，记T(N)=O(N3)。 “O”的形式定义为：若f(n)是正整数n的一个函数，则xn=O(f(n))表示存在一个正的常数M，使得当n=n0时都满足|xn|=M|f(n)| 空间复杂度 是程序运行所以需要的额外消耗存储空间,一般的递归算法就要有o(n)的空间复杂度了,简单说就是递归集算时通常是反复调用同一个方法，递归n次，就需要n个空间。（这个空间到底多大？我们姑且把它当作每次调用时分配的内存大小，到底多大，它自己确定）  我们在判读算法的优劣时，往往是综合考虑时间复杂度和空间复杂度两个因素，一般是希望能够找到两个都省的方法，但事实上我们往往需要牺牲时间复杂度来成全空间，或牺牲空间来节省时间。因此我们需要根据题目要求，选择侧重节省的因素。 更多的时候由于空间的耗费我们一般可以容忍，所以我们会更关注时间复杂度对算法的影响。 例:给出一个还有n个数的有序序列，要求查给定的一个数x是否在序列中，若在则给出所在序列中所处的位置。 输入：第一行输入两个数n和x 第二行为n个数 输出：x在序列中所处的位置的序号 样例：input： 6 61 12 35 58 60 61 100 output： 5 顺序查找 　? 从线性表的第一个元素开始，依次将线性表中的元素被查元素进行比较，若相等则表示找到（即查找成功）；若线性表中所有的元素都与被查元素进行比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。　 procedure search2(num:longint); var i,j:longint; begin for i:=1 to n do if a[i]=num then writeln(i); end; 二分查找法 　? 若中间项的值等于 x ，则说明查到，查找结束。　? 若 x 小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；　? 若 x 大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找； 　? 这个过程一直进行到查找成功或子表长度为 0 （说明线性表中没有这个元素）为止。　? procedure search(num:longin