推断合并排序的运行时间？
Extrapolating the runtime of mergesort?
我正在尝试解决以下问题，该问题要求我将合并排序的运行时间外推到更大的输入。问题是：
A user runs the code:
int a=(int*) malloc (N*sizeof(int));
for (i=0; i<N; i++)
{
a[i] = rand();
}
mergesort (a,N);
This code generates and then orders random numbers for N=10.000.000 and the time it needs is 5.3 sec
Assuming that we have enough memory, which of the following is closest to the runtime for N=1.000.000.000?
53, 340, 530, 680, 1060, 5300
我认为由于这是一种分而治之的方法，所以我们总共有 n log n 个拆分，对于 N=1.000.000.000 是 30。我知道合并排序的运行时间满足递归 T(n) = 2T(n / 2) + n，但是，我不知道如何使用它来推断运行时间。
我该如何解决这个问题？
mergesort 的运行时间是 Θ(n log n)。对于足够大的 n（就像你这里的数字），将运行时建模为 cn log n 形式的某些函数并不是不合理的。
解决此问题的一种方法是考虑 n = 109 的运行时间与 n = 107[ 的运行时间之比=27=]。这给了你
c 109 log 109 / c (107 log 107)
= 102 log 109 / log 107
= 102 (9 / 7)
= 128.6
因此，您预计 n = 109 的运行时间约为 n = 107[=27= 的运行时间的 128.6 倍].由于 n = 107 的运行时间为 5.3 秒，因此您预计 n = 109 的运行时间约为 681.6 秒。因此，列表中的最佳答案是 680s。
这种查看运行时间比率的方法是估算运行时间的一种很好的方法。我们也可以通过直接求解 c 来解决这个问题，因为运行时的形式是 cn log n 并且我们知道 n 的一个特定值的输出。我选择使用比率方法的原因是它通常有助于“观察”运行时。例如，由于运行时间为 Θ(n log n) 并且您将输入大小增加了 100 倍，因此可以合理猜测第 n 项的运行时间将至少增加 100 倍，那么可能一个更小的额外项放在 log n 项的顶部。仅此一项就可能让您猜测运行时间约为 680 秒。
希望对您有所帮助！
我正在尝试解决以下问题，该问题要求我将合并排序的运行时间外推到更大的输入。问题是：
A user runs the code:
int a=(int*) malloc (N*sizeof(int)); for (i=0; i<N; i++) { a[i] = rand(); } mergesort (a,N);This code generates and then orders random numbers for N=10.000.000 and the time it needs is 5.3 sec
Assuming that we have enough memory, which of the following is closest to the runtime for N=1.000.000.000?
53, 340, 530, 680, 1060, 5300
我认为由于这是一种分而治之的方法，所以我们总共有 n log n 个拆分，对于 N=1.000.000.000 是 30。我知道合并排序的运行时间满足递归 T(n) = 2T(n / 2) + n，但是，我不知道如何使用它来推断运行时间。
我该如何解决这个问题？
mergesort 的运行时间是 Θ(n log n)。对于足够大的 n（就像你这里的数字），将运行时建模为 cn log n 形式的某些函数并不是不合理的。
解决此问题的一种方法是考虑 n = 109 的运行时间与 n = 107[ 的运行时间之比=27=]。这给了你
c 109 log 109 / c (107 log 107)
= 102 log 109 / log 107
= 102 (9 / 7)
= 128.6
因此，您预计 n = 109 的运行时间约为 n = 107[=27= 的运行时间的 128.6 倍].由于 n = 107 的运行时间为 5.3 秒，因此您预计 n = 109 的运行时间约为 681.6 秒。因此，列表中的最佳答案是 680s。
这种查看运行时间比率的方法是估算运行时间的一种很好的方法。我们也可以通过直接求解 c 来解决这个问题，因为运行时的形式是 cn log n 并且我们知道 n 的一个特定值的输出。我选择使用比率方法的原因是它通常有助于“观察”运行时。例如，由于运行时间为 Θ(n log n) 并且您将输入大小增加了 100 倍，因此可以合理猜测第 n 项的运行时间将至少增加 100 倍，那么可能一个更小的额外项放在 log n 项的顶部。仅此一项就可能让您猜测运行时间约为 680 秒。
希望对您有所帮助！