插入排序与合并的时间
插入排序与合并的时间
提问于 2016-09-05 20:34:56
如果插入排序和合并对1000个元素所用的时间相同，比如说1秒，那么每种算法分别对10^6元素和10^9元素进行排序需要多长时间？
插入排序和合并的大O分别为n^2和n*log n。
这实际上是一个关于我的作业的附带问题，所以应该有一个可靠的答案。
请解释你的答案背后的理由。
回答 2
Stack Overflow用户
回答已采纳
发布于 2016-09-05 20:40:59
插入排序的时间复杂度为O(n^2)，因此时间尺度与要排序的元素的数量n成二次关系。如果n=1000需要1秒，那么n=10^6需要1*(10^6/1000)^2=10^6秒，n=10^9需要1*(10^9/1000)^2=10^12秒。Mergesort时间复杂度为O(n*log(n))。因此，可以相应地对时间进行缩放，发现n=10^6需要2000秒，n=10^9需要3*10^6秒。由于O(n^2)和O(n*log(n))都高于O(n)，所以我们可以忽略为合并排序分配额外的存储空间( O(n) )所需的时间，并且仅根据排序时间复杂度进行估计。希望这能有所帮助。
Stack Overflow用户
发布于 2016-09-05 20:41:59
我的回答是，这个问题无法回答，因为我们没有被告知任何元素的大小和合并将获得它所需要的工作记忆的方式。(插入排序需要常量的额外内存；合并需要O(n)附加内存。)如果元素是100 time，那么分配工作记忆将需要大量时间。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/39337368
复制相关文章
相似问题
腾讯云开发者
