algorithm - 时间复杂度计算

Question

我目前正在处理一些考试问题，但卡在了这一点上。我知道快速排序算法的时间复杂度为 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
• 我又一次陷入了困境。

Answer 1

我认为这个问题首先要注意的是，考虑到对数字进行排序需要 4 分钟，n 一定很大。例如，我刚刚在计算机上使用快速排序对 10 亿个数字进行排序，只用了不到 3 分钟。所以 n 可能大约为 10 亿(给出或接受一个数量级)。

鉴于 n 很大，对于某些常量 c，将此运行时间近似为 c*n*lg(n) 可能是合理的>，因为运行时扩展的低阶项不应该与如此大的 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 分钟长很多很多。