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

Question

可能吗？如果没有,给定一个大小为n的数组,我怎么知道它是否更好地排序数组？

Answer 1

随着刚刚在无序数组,就没有办法在亚线性时间做到这一点.由于您不知道哪个元素是最大和最小的,因此您必须全部查看它们,因此需要线性时间.

你会发现最好的排序会比这更糟糕,可能相对于n log n这样做线性扫描会"更好".

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

• 将值添加到空列表时,将min和max设置为该值.恒定时间O(1).
• 将值添加到非空列表时,如果适用,请将min或max设置为该值.恒定时间O(1).
• 从列表中删除值时,如果要删除的值等于当前最小值或最大值,则将min或max设置为"unknown".恒定时间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

鉴于一般问题:

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

我无法想象任何能够实现这一目标的机制.

但是,如果您保持对最小值和最大值的引用并更新每个插入/追加/替换操作的值,则最小/最大查找的摊销成本可能非常便宜.

与简单的线性扫描相比,对阵列进行排序非常昂贵,以找到最小值和最大值,因此只有在有其他好处时才进行排序.(当然,插入排序可以提供非常类似的属性来更新每个插入/追加/替换操作的最小值和最大值,因此它可能是可接受的.)