以排序顺序维护数字列表的时间和空间复杂度（即从第一个插入它开始，第二个随之而来，您按排序顺序插入它等等..）是否与在它们出现时插入它们相同然后在所有插入完成后排序？
我该如何做出这个决定？你能证明'n'个元素的时间和空间复杂度吗？
我在考虑电话簿，每次将记录插入电话簿时将其存储在集合中并向用户呈现排序数据与将电话簿记录按排序顺序存储在树集中有什么区别。n 个元素会是什么？
问问题
5783 次
4 回答
3
每次你插入一个排序列表并保持它的排序时，它是 O(logn) 比较来找到它的放置位置，但是 O(n) 移动来放置它。因为我们插入了 n 个元素，所以这是 O(n^2)。但是，我认为，如果您使用设计用于将排序数据插入（例如二叉树）的数据结构，然后在最后进行传递以将其转换为列表/数组，则只需 O(nlogn)。另一方面，使用这种更复杂的数据结构将使用大约 O(n) 的额外空间，而所有其他方法都可以就地完成并且不使用额外的空间。
每次插入未排序列表时都是 O(1)。最后对它进行排序是 O(nlogn)。这意味着总体上它是 O(nlogn)。
但是，如果您不打算列出许多元素（1000 或更少），那么它是什么大 O 可能并不重要，您应该专注于小数据集运行速度更快的东西，或者根本不用担心如果不是性能问题。
于 2013-06-24T04:57:31.503 回答
2
这取决于您将它们插入到什么数据结构中。如果您询问插入数组，答案是否定的。存储 n 个元素需要 O(n) 空间和时间，然后对它们进行排序需要 O(n log n)，因此总共需要 O(n log n)。插入数组时可能需要移动 \Omega(n) 元素，因此需要 \Theta(n^2)。大多数“顺序”数据结构也会出现同样的问题。对不起。
另一方面，一些优先级队列，如惰性左派堆、斐波那契堆和 Brodal 队列具有 O(1) 插入。同时，手指树提供 O(n log n) 插入和线性访问（对于链表的好处而言，手指树与链表一样好，而对于二叉搜索树的好处而言，手指树与平衡二叉搜索树一样好——他们有点神奇）。
于 2013-06-24T04:57:18.940 回答
1
算法选择将存在特定于应用程序的权衡。插入排序维基百科页面上列举了可能使用插入排序而不是某种离线排序算法的原因。
这里的决定因素不太可能是渐近复杂性，而更有可能是您对数据的了解（例如，它可能已经排序了吗？）
我会更进一步，但我不相信这不是逐字询问的家庭作业问题。
于 2013-06-24T04:56:54.233 回答
-1
选项1
按排序顺序插入正确位置。
找到第 i+1 个元素的位置所需的时间：O(logi)
插入和维护第 i+1 个元素的顺序所需的时间：O(i)
空间复杂度：O(N)
总时间：(1*log 1 +2*log 2 + .. +(N-1)*logN-1)=O(NlogN)
了解这只是时间复杂度。运行时间可能与此有很大不同。
选项 2：
插入元素O(1)
对元素进行排序O(NlogN)
根据您使用的排序，空间复杂度会有所不同，尽管您可以使用快速排序之类的东西，无论如何它不需要太多空间。
总之，虽然两个时间复杂度是相同的，但界限很弱，在数学上你可以想出更好的界限。另外请注意，在实际情况下可能永远不会遇到最坏情况的复杂性，可能你只会看到平均情况。如果性能在您的应用程序中是一个如此重要的问题，您应该在随机抽样时测试两组代码。请告诉我在您的测试后哪一个运行得更快。我的猜测是选项 1。
于 2013-06-24T06:37:32.293 回答