查找算法的比较 策略 一 -步数与n成正比 一称为线性时间算法 策略二 - 步数与log2n成正比 一称为对数时间算法 0 猜数游戏中：若数的范围是1~1000000，则 -策略一：平均要猜50万次才能猜对 人最坏1百万次，最好1次 -策略二：最坏也只需猜20次 Lu Chaojun,SJTU 6Lu Chaojun, SJTU 6 查找算法的比较 • 策略一 – 步数与n成正比 – 称为线性时间算法 • 策略二 – 步数与log2 n成正比 – 称为对数时间算法 • 猜数游戏中:若数的范围是1~1000000,则 – 策略一:平均要猜50万次才能猜对 ©最坏1百万次,最好1次 – 策略二:最坏也只需猜20次