8

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

4

4 回答 4

9

只有未排序的数组，没有办法在亚线性时间内做到这一点。由于您不知道哪个元素是最大和最小的，因此您必须查看它们，因此是线性时间。

你会发现最好的排序会比这更糟，可能相对于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. 在正确设计的系统中，它们当然是实例变量，因此您可以并排运行多个列表。

于 2011-12-04T10:31:15.277 回答
5

鉴于一般问题：

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

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

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

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

于 2011-12-04T09:58:29.063 回答
2

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

于 2011-12-04T09:59:43.440 回答
0

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

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

于 2012-11-24T10:49:50.243 回答