同步阅读进度,多语言翻译,过滤屏幕蓝光,评论分享,更多完整功能,更好读书体验,试试 阅读 ‧ 电子书库
分析
如果寻找的元素属于集合并且在任意索引位置的概率是相等的(换句话说,它被迭代器在任意位置找到的几率是相等的),那么这就是平均情况下顺序查找(如我们在第2章所述)。
也就是说,对于每个目标元素来说,你将需要寻找集合中大约一半的元素。最好情况即待查找的元素是集合中的第一个。算法在最坏和平均情况下都是线性增长的。如果你加倍集合的大小,那么查找的时间也大约会是两倍。
为了得到顺序查找的实际性能,我们构造了一个包含n个整数(范围为[1,n])的有序集合。虽然这个集合是有序的,但是查找时并没有用到这个信息。我们将会进行100次试验;每一次试验我们执行1000次查找随机值t。我们抛弃最好和最坏的结果,然后对剩余的结果取平均值。表5-1是四个特定的p值,剩余98次的平均时间。注意当集合的大小加倍时,执行时间也大约加倍。你也需要看到,对每一种输入集合的大小来说,最后一列表示最坏情况的时间。
在最好情况下,集合的第一个元素就是需要的元素,这样仅仅需要花费O(1)常数时间。最坏的情况是寻找的元素不在集合中,在这种情况下,你需要检查集合中的所有元素,导致了O(n)的性能,平均情况下(如第2章所述,并且如表5-1所示),性能是O(n)。
请支持我们,让我们可以支付服务器费用。
使用微信支付打赏