9 i查找方向算法 3.1 ——顺序查找 int SeqSearch1 ( int r[ ], int n, int k ) //数组 r[1] ~ r[n] 存放查找集合{ i=n; while ( i>0 && r[i]!=k ) i --; return i; } 算法 3.1 的基本语句是 i>0 和 r[i]!=k ,其执行次数为:?????????????????? ni ni ni ni iiii nOninn inn cpbp 11 11)(1)1( 1)1( 1 基本语句? 将待查值放在查找方向的尽头处,免去了在查找过程中每一次比较后都要判断查找位置是否越界,从而提高了查找速度。 k 10 15 24 6 12 35 40 98 55 0 1 2 3 4 5 6 7 8 9 i查找方向哨兵改进的顺序查找算法 3.2 ——改进的顺序查找 int SeqSearch2(int r[ ], int n, int k) //数组 r[1] ~ r[n] 存放查找集合{ r[0]=k; i=n; while (r[i]!=k) i --; return i; }算法 3.2 的基本语句是 r[i]!=k ,其执行次数为: ?????????? ni ni iinO ninn cp 1 1)(2 1)1( 1 数量级相同, 系数相差一半用蛮力法设计的算法,一般来说,经过适度的努力后,都可以对算法的第一个版本进行一定程度的改良,改进其时间性能,但只能减少系数,而数量级不会改变。?一般观点:
全文预览