插入排序与合并排序的时间
Time for insertion sort vs mergesort
如果插入排序和归并排序对 1000 个元素花费相同的时间，比如说 1 秒，那么每个算法分别对 10^6 个元素和 10^9 个元素进行排序需要多长时间？
插入排序和归并排序的大O分别是n^2和n*log n。
这实际上是我作业中的一个附带问题，所以应该有一个可靠的答案。
请解释你的回答背后的理由。
插入排序的时间复杂度为 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 秒。合并排序的时间复杂度是 O(n*log(n))。因此可以相应地缩放时间以发现 n=10^6 需要 2000 秒，而 n=10^9 需要 3*10^6 秒。由于 O(n^2) 和 O(n*log(n)) 都高于 O(n)，我们可以忽略，比方说，为合并排序分配额外存储空间 space O(n) 所需的时间在大 n 限制和估计完全基于排序时间复杂度。希望这会有所帮助。
我的回答是这个问题无法回答，因为我们没有被告知任何关于元素大小和归并排序获取所需工作内存的方式的信息。 （插入排序需要恒定的额外内存；合并排序需要 O(n) 额外内存。）如果元素是 100KiB，那么分配工作内存将花费大量时间。
如果插入排序和归并排序对 1000 个元素花费相同的时间，比如说 1 秒，那么每个算法分别对 10^6 个元素和 10^9 个元素进行排序需要多长时间？
插入排序和归并排序的大O分别是n^2和n*log n。
这实际上是我作业中的一个附带问题，所以应该有一个可靠的答案。
请解释你的回答背后的理由。
插入排序的时间复杂度为 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 秒。合并排序的时间复杂度是 O(n*log(n))。因此可以相应地缩放时间以发现 n=10^6 需要 2000 秒，而 n=10^9 需要 3*10^6 秒。由于 O(n^2) 和 O(n*log(n)) 都高于 O(n)，我们可以忽略，比方说，为合并排序分配额外存储空间 space O(n) 所需的时间在大 n 限制和估计完全基于排序时间复杂度。希望这会有所帮助。
我的回答是这个问题无法回答，因为我们没有被告知任何关于元素大小和归并排序获取所需工作内存的方式的信息。 （插入排序需要恒定的额外内存；合并排序需要 O(n) 额外内存。）如果元素是 100KiB，那么分配工作内存将花费大量时间。