我对性能分析感到困惑 binarySearch 来自 集合
它说：
如果指定的列表未实现RandomAccess接口 并且很大，这个方法会做一个基于迭代器的二进制搜索 执行O（n）链接遍历和O（log n）元素比较。
我不知道如何解释这一点 O(n) + O(log n)。
我的意思是，这不仅仅是简单地遍历链表并进行比较吗？我们仍然只有 O(n)。
那么这句话对绩效意味着什么呢？如上所述，我无法理解与链表中的简单线性搜索的区别。
我在这里误解了什么？
我对性能分析感到困惑 binarySearch 来自 集合
它说：
如果指定的列表未实现RandomAccess接口 并且很大，这个方法会做一个基于迭代器的二进制搜索 执行O（n）链接遍历和O（log n）元素比较。
我不知道如何解释这一点 O(n) + O(log n)。
我的意思是，这不仅仅是简单地遍历链表并进行比较吗？我们仍然只有 O(n)。
那么这句话对绩效意味着什么呢？如上所述，我无法理解与链表中的简单线性搜索的区别。
我在这里误解了什么？
首先，你必须明白没有 RandomAccess 接口 binarySearch 不能简单地从列表中访问随机元素，而是必须使用迭代器。那介绍 O(n) 成本。当集合实现时 RandomAccess，每个元素访问的成本是 O(1) 就渐近复杂性而言，可以忽略不计。
因为 O(n) 大于 O(log n) 它总是优先于 O(log n) 并支配复杂性。在这种情况下 binarySearch 具有与简单线性搜索相同的复杂性。 那有什么好处呢？
线性搜索执行 O(n) 比较，而不是 O(log n) 同 binarySearch 没有随机访问。这在常数之前尤为重要 O(logn) 高。用简单的英语： 当单个比较与推进迭代器相比具有非常高的成本时。这可能是非常常见的情况，因此限制比较的数量是有益的。利润！
首先，你必须明白没有 RandomAccess 接口 binarySearch 不能简单地从列表中访问随机元素，而是必须使用迭代器。那介绍 O(n) 成本。当集合实现时 RandomAccess，每个元素访问的成本是 O(1) 就渐近复杂性而言，可以忽略不计。
因为 O(n) 大于 O(log n) 它总是优先于 O(log n) 并支配复杂性。在这种情况下 binarySearch 具有与简单线性搜索相同的复杂性。 那有什么好处呢？
线性搜索执行 O(n) 比较，而不是 O(log n) 同 binarySearch 没有随机访问。这在常数之前尤为重要 O(logn) 高。用简单的英语： 当单个比较与推进迭代器相比具有非常高的成本时。这可能是非常常见的情况，因此限制比较的数量是有益的。利润！
二进制搜索不适用于链接列表。该算法应该受益于 随机访问排序的集合 （像一个普通的数组），它可以快速地从一个元素跳转到另一个元素，在每次迭代时将剩余的搜索空间分成两部分（因此 O(log N) 时间复杂度）。
对于链表，有一个修改版本，它遍历所有元素（需要经过 2n 最糟糕的情况下的元素），但它不是比较每个元素，而是仅仅在指定的位置“探测”列表（因此数量较少） 对比 与线性搜索相比）。
由于与普通指针迭代相比，比较通常略微昂贵，因此总时间应该更低。这就是为什么 log N 部分分别强调。