关于排序的问题

Question

冒泡排序最多为O(n),最差为O(n ^ 2),其内存使用量为O(1).合并排序始终为O(n log n),但其内存使用量为O(n).

我们将使用哪种算法来实现一个取整数数组并返回集合中最大整数的函数,假设数组的长度小于1000.如果数组长度大于1000怎么办？

Answer 1

在O(n)时间内使用O(1)存储器使用,可以在O(n)时间内完成数据集的顺序扫描,寻找最大值.

您只需将当前最大值设置为第一个元素,然后运行所有其他元素,如果值更大,则将当前最大值设置为该值.伪代码:

max = list[first_index]
for index = first_index+1 to last_index:
    if list[index] > max:
        max = list[index]

的复杂性也不会因元素的数量在列表中,这样也没关系有多少改变.

然而,运行时间将改变(因为算法是O(n)时间),并且如果找到最大快速是重要的,则存在许多可能性.这些都取决于列表更改时的工作,而不是每次您需要信息时,因此它们更适合读取比写入更频繁的列表,因此可以分摊成本.

选项1是保持列表排序,以便您可以抓住最后一个元素.这可能是矫枉过正的只是保持最大的记录.

选项2是在插入或删除列表时重新计算最大值(以及保留它的元素数).最初设置max为0,maxcount为空列表设置为0 .

对于插入:

• 如果maxcount为0(列表为空),则设置max为此值并设置maxcount为1.
• 否则,如果此值大于max,则设置max为此值并设置maxcount为1.
• 否则,如果此值等于max,则将1添加到maxcount.

删除:

• 如果此值等于max,则从中减去1 maxcount.
• 然后,如果maxcount是0,重新扫描列表以获得新的max和maxcount.

这样,在任何时候,你都有最大值(计数只是一个额外的"技巧"来加速算法,其中有多个元素保持最大值).我曾经在数据分析应用程序中使用过一次,结果比重新排序快得多 - 在这种情况下我必须存储最小值和最大值,但这是相同的想法.