arrays - 复杂度为 O(log n) 的搜索算法，UNSORTED 列表/数组

Question

我在一次考试中做了这个练习，它说:

Find an algorithm which can search for the highest number in an unsorted list and have a Big-Oh complexity of O(log(N)).

我发现的唯一具有 log n 复杂度的搜索算法是二分搜索算法，但该算法需要对列表/数组进行排序。

有这样的算法吗？

Answer 1

这是一个有技巧的问题。没有说明列表有 N 个元素。因此，您可以使用变量的更改，并将 N 替换为 2^K。现在，使用线性算法解决具有 K 个元素的列表的问题。

如果我们假设列表中有 N 个元素，一个可能的解决方案是使用 N 个并行计算元素 [ CE₀ .. CE_N ]。在算法的基本情况下，我们让每个计算元素 CE_i 在 [ CE_N/2 .. CE_N ] 比较列表值 x_2i-N 和 x_2i-N+1。每个计算元素向 CE_i/2 报告其两个分配值中较大的一个。该算法的迭代步骤是每个接收到两个报告值的计算单元CE_k报告最大的到CE_k/2 。这种迭代逻辑一直持续到 CE₀ 处理来自自身的报告。它不再向自己报告，而是输出结果。

如果排除并行计算，则问题无解。