algorithm - 维护排序列表与插入所有值然后排序的复杂性

Question

按排序顺序维护数字列表的时间和空间复杂度是否与插入它们相同(即从第一个插入它，第二个出现，你按排序顺序插入它等等......)当它们出现然后在所有插入完成后排序？

我如何做出这个决定？你能证明“n”个元素的时间和空间复杂度吗？

我在考虑电话簿方面的问题，将它存储在一个集合中并在用户每次向电话簿中插入一条记录时向用户呈现排序数据与将电话簿记录按排序顺序存储在树集中有什么区别。 n 个元素会是什么？

Answer 1

每次插入一个排序列表并保持其排序时，需要 O(logn) 次比较才能找到放置它的位置，但要进行 O(n) 次移动才能放置它。因为我们插入 n 个元素，所以这是 O(n^2)。但是，我认为，如果您使用专为插入排序数据而设计的数据结构(例如二叉树)，然后在最后执行一次传递以将其转换为列表/数组，则它只是 O(nlogn)。另一方面，使用这样一个更复杂的数据结构将使用大约 O(n) 的额外空间，而所有其他方法都可以就地完成并且不使用额外的空间。

每次插入未排序的列表都是 O(1)。最后对它进行排序是 O(nlogn)。这意味着总的来说它是 O(nlogn)。

但是，如果您不打算列出许多元素(1000 个或更少)，那么它是什么大 O 可能并不重要，您应该关注小数据集运行速度更快的东西，或者不如果这不是性能问题，根本不用担心。