Cra*_*lus 11 java algorithm collections complexity-theory list
我binarySearch对收藏品的性能分析感到困惑
它说:
如果指定的列表没有实现RandomAccess接口并且很大,则此方法将执行基于迭代器的二进制搜索,该搜索执行O(n)链接遍历和O(log n)元素比较.
我不知道如何解释这个O(n)+ O(log n).
我的意思是,这不仅仅是简单地遍历链表并进行比较吗？我们仍然只得到O(n).
那么这句话对绩效意味着什么呢？如上所述,我无法理解链表中的简单线性搜索的区别.
我在这里误解了什么？
Tom*_*icz 11
首先,你必须明白,如果没有RandomAccess接口,binarySearch就不能简单地从列表中访问随机元素,而是必须使用迭代器.这引入了O(n)成本.当集合实现时RandomAccess,O(1)就渐近复杂性而言,每个元素访问的成本是并且可以被忽略.
因为它总是O(n)超过O(log n)它将始终优先于O(log n)并支配复杂性.在这种情况下,binarySearch具有与简单线性搜索相同的复杂性.那有什么好处呢？
线性搜索进行O(n)比较,而不是O(log n)与binarySearch没有随机访问.当前面的常数O(logn)很高时,这一点尤为重要.简单来说:与推进迭代器相比,单一比较的成本非常高.这可能是非常常见的情况,因此限制比较的数量是有益的.利润!