我可以在亚线性时间内找到未排序数组中的最大/最小值吗？

Question

是否可以？如果不是，给定一个大小为 n 的数组，我如何知道对数组进行排序是否更好？

Answer 1

仅使用未排序的数组，无法在亚线性时间内完成此操作。由于您不知道哪个元素最大和最小，因此您必须查看所有元素，因此需要线性时间。

您会发现的最佳排序会比这更糟糕，可能相对于n log n，因此进行线性扫描会“更好”。

如果允许您存储更多信息，还有其他方法可以加快该过程。您可以使用以下规则存储最小值和最大值：

• 将值添加到空列表时，将最小值和最大值设置为该值。常数时间 O(1)。
• 将值添加到非空列表时，如果合适，请将 min 或 max 设置为该值。常数时间 O(1)。
• 从列表中删除值时，如果要删除的值等于当前的最小值或最大值，请将最小值或最大值设置为“未知”。常数时间 O(1)。如果您同时存储最小值/最大值及其计数，您还可以提高效率。换句话说，如果您的列表有当前最大值的七个副本，并且您删除了一个，则无需将最大值设置为未知，只需减少计数即可。仅当计数达到零时才应将其标记为未知。
• 如果您要求空列表的最小值或最大值，请返回一些特殊值。常数时间 O(1)。
• 如果您要求已知值的非空列表的最小值或最大值，请返回相关值。常数时间 O(1)。
• 如果您要求值未知的非空列表的最小值或最大值，请执行线性搜索来发现它们，然后返回相关值。线性时间 O(n)。

通过这样做，可能绝大多数检索最小值/最大值都是恒定时间。仅当您删除了最小值或最大值的值时，下一次检索才需要一次检索的线性时间。

此后的下一次检索将再次是常数时间，因为您已经计算并存储了它们，假设您没有再次删除中间的最小/最大值。

---

仅求最大值的伪代码可能很简单：

def initList ():
    list = []
    maxval = 0
    maxcount = 0

在上面的初始化代码中，我们只需创建列表以及最大值和计数。添加最小值并进行计数也很容易。

要添加到列表中，我们遵循上述规则：

def addToList (val):
    list.add (val) error on failure

    # Detect adding to empty list.
    if list.size = 1:
        maxval = val
        maxcount = 1
        return

    # If no maximum known at this point, calc later.
    if maxcount = 0:
        return

    # Adding less than current max, ignore.
    if val < maxval:
        return

    # Adding another of current max, bump up count.
    if val = maxval:
        maxcount += 1
        return

    # Otherwise, new max, set value and count.
    maxval = val
    maxcount = 1

删除非常简单。只需删除该值即可。如果是最大值，则减少这些最大值的计数。请注意，只有当您知道当前最大值时，这才有意义 - 如果不知道，则您已经处于必须计算它的状态，因此只需保持该状态即可。

计数变为零将表明最大值现在未知（您已将它们全部删除）：

def delFromList (val):
    list.del (val) error on failure

    # Decrement count if max is known and the value is max.
    # The count will become 0 when all maxes deleted.
    if maxcount > 0 and val = maxval:
        maxcount -= 1

获得最大值就是知道何时需要计算它（当 maxcount 为零时）。如果不需要计算，只需返回它：

def getMax ():
    # raise exception if list empty.
    error if list.size = 0

    # If maximum unknown, calculate it on demand.
    if maxcount = 0:
        maxval = list[0]
        for each val in list:
            if val = maxval:
                maxcount += 1
            elsif val > maxval:
                maxval = val
                maxcount = 1

    # Now it is known, just return it.
    return maxval

所有伪代码都使用看似全局变量，list、maxval和maxcount 。在正确设计的系统中，它们当然是实例变量，以便您可以并排运行多个列表。

Answer 2

鉴于一般性问题：

我可以在亚线性时间内找到未排序数组中的最大/最小值吗？

我无法想象有什么机制可以实现这一点。

但是，如果您保留对最小值和最大值的引用并在每次插入/追加/替换操作时更新这些值，则最小/最大值查找的摊销成本可能非常便宜。

与寻找最小值和最大值的简单线性扫描相比，对数组进行排序的成本非常，因此只有在有其他好处时才进行排序。 （当然，插入排序可以提供非常相似的属性来更新每个插入/追加/替换操作的最小值和最大值，因此它可能是足够可以接受的。）

Answer 3

对于未排序的数组，最小/最大复杂度为 O(N)。没有办法超越它。对于排序数组 0(1) 但排序为 0{N log N)。如果您需要仅搜索最小/最大或接近它的排序是没有用的。但是，如果您多次执行此操作，请查看一些搜索结构（例如 Rb 树或堆）以重新组织日期，以避免搜索中的线性时间。

Answer 4

在这个完整的答案（使用C++代码）中，我在这里找到 - 从数字数组中获取最小值或最大值的最佳方法是什么- com - 它清楚地表明，如果 n 为偶数，则总比较次数为3n/2 - 2（对于奇数，常数为 3/2 ） 。

因此，在忽略对足够大的 n 没有影响的 2 个常量（限定符 3/2 和 -2 ）之后，它显然属于 O(n) 并且它是就复杂性而言是线性的，但就效率而言（如果我可以这么说的话）它是 1.5n 并且非常出色