实现 O(1) 的 Max 算法

Question

我被要求实现一个简单的算法来找到列表中具有一个重要条件的最大数字。该算法应该是 O(1)。所以我写了这个：

int max = Int32.MinValue;
foreach (int item in _items)
{
    if (item.CompareTo(max) > 0)
        max = item;
}

return max;

正如评论部分中有人指出的那样，这是 O(N)。但是如何使用复杂度为 O(1) 的算法找到列表中的最大数。因为对我来说，您似乎必须迭代所有数组项才能找到最大数量。这可能吗？

Answer 1

您可以维护一个包含列表中最高值的变量。当您 insert/delete 时，您会跟踪该值。

那么你的max函数可以是O(1):

def max(): return max_value

这增加了 insert/delete 的工作量，但满足您指定的 max() 在恒定时间内运行的要求。

Answer 2

就像评论者所说的那样，除非您维护一个 max 变量并在每次插入操作时更新它，否则这是不可能的：

Insert(element)  
    If element > max  
        max = element  
    (Rest of insertion code)

这样你可以 return 在 O(1) 中最大

[编辑]
如果我正确理解您的局限性，您需要一个解决方案：
O(1) - 插入
O(1) - 删除
O(1) - 获取最大值
O(1) - 检索

不确定是否存在这样的算法，但关注此线程以查看我是否可以学到新东西 (;

Answer 3

堆数据结构可能就是您要找的。基本版本查找最大 O(1)，插入和删除 O(log N)。 Fibonacci 堆也有插入 O(1)。见 Wikipedia article.

Answer 4

在考虑了您的原始问题以及您的评论（以及我想的一些推论）之后，您的要求如下：

一个类似列表的数据结构
O(1) 次随机访问
O(1) 最后插入（摊销）
O(1) 最后删除（摊销）
O(1) 最大值

最直接的解决方案（跟踪插入时的最大元素）无法满足要求 4，因为您需要重新计算删除时的最大值。那么我们可以通过调整来解决这个问题吗？

是的，我们可以！我们不是只跟踪总最大值，而是跟踪所有索引 i 的最大值 i。所以每次我们附加到列表时，我们都会向列表添加一个条目，其中包含值以及新的最大值。因此，为了获得总最大值，我们在最后一个索引处取最大值。要删除最后一个元素，我们只需删除最后一个条目。为了获得索引 i 处的元素，我们获取索引 i 处的条目和 return 它的值。因此，只要底层数据结构在（分摊的）O(1) 中执行这些操作（例如，ArrayList 会），我们也是如此。

实现 O(1) 的 Max 算法

Implementing a Max algorithm that is O(1)

performance

big-o