如何确定哪个算法的运行时间是log n

Question

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

Answer 1

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

如果你有一个顺序的，有序的列表，你做一个二分查找，每次比较减少1/2可能的位置匹配。

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