我目前正在处理一些考试问题，并在此时陷入困境。我得到一个Quicksort算法的时间复杂度为O(nlog(n))。对于特定的输入大小，对列表进行排序的时间为4分钟。问题继续询问在同一系统上对两倍大小的列表进行排序需要多长时间。
我已经排除了时间不是8分钟的问题（输入大小的两倍=持续时间的两倍，这是非常错误的推理）。
我做了一些工作：
工作A
4 = nlog(n)4 = log(n^n)16 = n^n工作B
X = 2nlog(2n) >> 2n 因为输入两倍X = 2n(1 + log(n))X = 2n + 2nlog(n) >> nlog(n)是4几分钟X = 2n + 2(4) = 2n + 8我认为关于此问题的第一件事是，鉴于对数字进行了4分钟的排序，它n必须很大。例如，我只是使用quicksort在计算机上对十亿个数字进行排序，而这只花了不到3分钟的时间。所以，n可能是大约十亿（给予或采取一个数量级）。
鉴于这n是巨大的，因此c*n*lg(n)对于某个常量近似地估计此运行时可能是合理的c，因为运行时扩展的低阶项对于这么大的范围应该不太相关n。如果加倍n，则将原始运行时的运行时间乘以以下乘数：
[Runtime(2n)] / [Runtime(n)]
[c * (2n) * lg(2n)] / [c * n * lg(n)]
2 * lg(2n) / lg(n)
2 * log_n(2n)
2 * (1 + log_n(2))
在这里，lg()是在任意底数下的对数，并且log_n()是对数底数n。
首先，由于我们假定n较大，因此一种可行的处理方式是将其近似log_n(2)为0，因此运行时乘数将近似为2，而总运行时将近似为8分钟。
或者，由于我们可能知道n一个数量级，因此另一种可能性是将乘数近似为n：
n= 1亿，则乘数约为2.075，总运行时间约为8.30分钟。n= 10亿，则乘数约为2.067，总运行时间约为8.27分钟。n= 100亿，则我们将乘数近似为2.060，总运行时间为8.24分钟。请注意，在我们的n收益率近似中的巨大变化在总运行时间的近似中产生了很小的变化。
值得注意的是，尽管在纸面上看起来不错，但实际上，体系结构方面的考虑可能会导致实际运行时与我们在此处计算出的运行时有很大不同。例如，如果算法在将数据大小增加一倍后引发一堆分页，则运行时间可能比我们在此处估算的大约8分钟要高得多。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句