我希望对顺序到来的元素进行排序,也就是说,在下一个元素进入之前,我希望我的向量已经排序好了。我知道插入排序的复杂度为n^2,如果我有总计n个元素。归并排序应该更好一些。然而,通常会说归并排序的复杂度为n log n;但是我猜想,如果你要逐个地排序n个元素,并且需要将临时向量排序,那么复杂度会上升到\sum_{i=2}^n i log(i)。我想这仍然比n^2要小,但绝对比n log n大。
我说得对吗?
谢谢。
我说得对吗?
谢谢。
EDIT 2:
\sum_{i=1}^N i log i > \sum_{i=1}^N i = O(N²)
编辑:显然,你没有理解重点,所以我会尝试澄清。
首先,在每次插入后确保数组排序的情况下,将N个元素插入到数组中可以在O(N²)的复杂度内完成。您可以使用以下算法来插入一个元素:
对于N次插入重复使用此算法,从而得到\sum_i (i + log i) = O(N²)。
为了使其非常清楚:这不是插入排序。插入排序将涉及重新插入所有元素以对整个数组进行排序,而此算法仅插入一个元素。
其次,执行此操作不能比O(N²)更快:将一个元素插入到大小为i的数组中并保持数组排序的复杂度大于O(i),因为它涉及移动多达i个元素。 没有绕过这个基本事实的方法:如果您将1
插入到[2,3,..,i]
中,则结果为[1,2,3,..,i]
,这意味着必须移动元素2、3 .. i 。
因此,总和大于\sum_i i = O(N²)。