如何以 O(n log n) 时间复杂度找到输入大小每单位变化所带来的运行时间变化？

Question

如果程序的运行时间为 4.956 秒，输入大小为 10,000,000，那么如果我将输入大小增加到 20,000,000，时间复杂度为 O(n log n)（大约运行时间），运行时间会是多少？

Answer 1

假设启动时间可以忽略不计，该比率应约为

(2n.log(2n))/(n.log(n))

简化为

(2.(log(n) + log(2)))/log(n)

2.(1 + log(2)/log(n))

因此，从 10 到 2000 万，比率略高于 2，约为 2.043，因此大约 10.13s。