简单查找:最多需要100步 二分查找:最多需要7步
当我们要查找的有240000元素的字典,使用二分查找,每次排除一般单词,最多只需18步。...一般而言,对于包含n个元素的列表,使用二分查找最多需要log2n步,而简单的查找需要n步。...[10]={0,1,2,3,4,5,6,7,8,120};
int binary_search(int *p, int target, int len)
{
int times;//记录查找次数...练习题
假设有一个包含128个名字的有序列表,你要使用二分查找在其中查找一个名字,请 问最多需要几步才能找到?
log(2)128 = 7 7次
上面列表的长度翻倍后,最多需要几步?...8步
大O表示法
算法的运行时间以不同的速度增加
简单查找 二分查找
100个元素 100ms 1ms
10000个元素 10s 14ms
1000000000个元素 11天 32ms
① 仅知道算法需要多长时间才能运行完毕还不够