-1
50万个有序的数据中查找一个key, 使用的是 O(logN) 的算法, 简单来说就是二分查找,在我的理解中O(logN)就是在一颗平衡的二叉树中查找一个数据, 数据结构可能不同,但是形式是一样的,就是把数据分成两份,不断的分成2份

1.那么50W有序的数据使用O(logN)算法查找,如何计算出最坏的情况下,需要查找多少次,才能找到数据?

"我目前知道的O(logN)的理解:
当数据增大n倍时,耗时增大logN倍,log以2为底
当数据增大8倍时:
8 = log(2) ^ 3, 所以数据增大8倍,耗时只增大3倍"
seq_ack 117
6月19日提问
5 个回答
0

已采纳

O(logN) = 2^n >= N 那么最坏就需要查找n次
50W = 2^19 = 524288 >= 500000 = 19 最坏需要查找19次

1

都知道了logN,N不就是50w么,你不回算,打开计算器算下log(50w)

1

1:查找多少次由你的算法分治决定,公式就是X=log(分治数)(50W),二分法就是2,以此类推
2:时间公式就是你下面写的,但是每台机器运算时间都不一样,所以只能得到你机器的基础时间,比如用1000个数据运算一次,得出基础时间,后面50W是1000的多少倍就可以代入你上面的公式。

0

这有什么不能计算的? 随机构造1000个这样的50w个数据, 开始计时, 查找, 记录时间和次数. 最后统计总数据/1000不就是了吗?

0
  1. 数据在录入时是否使用了有序的数据结构,比如使用了红黑树或堆。
  2. 如果没有使用有序数据结构,那么是否使用了排序算法。
  3. 在排序的基础上进行lgN算法查找,lgN中N增加n倍,那么数学运算就是 nlgN。

撰写答案

推广链接