linked-list - 如何确定哪个算法的运行时间为 log n

Question

老师告诉我们，每次除以 2 时，运行时间很可能是 log n。例如，如果我们将一个数组一分为二，每次遍历其中一个数组时，运行时间将是 log n。但是，我们可能会遇到 LinkedList 很容易被误导的情况。例如，我们可能有一个算法来通过从头部或尾部开始来找到列表的最大值，以使运行时间小于 n。从逻辑上讲，我们可能认为运行时间是 log n，但事实并非如此。这是为什么？你如何确定？

Answer 1

从前面或后面（或交替）开始不会改变搜索最大值的基础。它所做的只是重新排序搜索策略。

如果您有一个顺序的、有序的列表并进行二分搜索，则每次比较都会将匹配的可能位置减少 1/2。

如果您查看链表的一个元素，每次比较都会将匹配的可能位置减少 1 个元素。

这是一个至关重要的区别。