2

输入大小为 100 的算法需要 0.5 ms 秒，如果输入大小为 500 且程序为 O(n lg(n))，则运行需要多长时间？

我的书说，当输入大小加倍时，n lg(n) 需要“略多于两倍的时间”。这对我帮助不大。

我一直这样做的方式是求解常数乘数（这本书没有谈到，所以我不知道它是否有效）：

.5ms = c * 100 * lg(100) => c = .000753

所以

.000753 * 500 * lg(500) = 3.37562ms

这是计算运行时间的有效方法吗，有没有更好的方法来计算它？

4

2 回答 2

1

是的。这正是它的工作原理。

当然，这忽略了任何可能的初始化开销，因为这没有在 big-o 表示法中指定，但这与大多数算法无关。

于 2009-10-02T18:21:40.960 回答
1

那不完全正确。托马斯说得对，有开销，真正的方程更像

runtime = inputSize * lg(inputSize) * singleInputProcessTime + overhead

singleInputProcessTime 与机器操作有关，例如加载地址空间、算术或每次与输入交互时必须完成的任何事情。这通常具有从几个 CPU 周期到几秒钟或几分钟不等的运行时间，具体取决于您的域。重要的是要了解这个时间大致是恒定的，因此在输入大小足够大时不会对整体运行时间产生太大影响。

开销是设置问题/解决方案的成本，例如将算法读入内存，在服务器/进程之间传播输入或任何只需要发生一次或不依赖于输入大小的设定次数的操作。此成本也是恒定的，范围从几个 CPU 周期到几分钟不等，具体取决于用于解决问题的方法。

inputSize 和 n * lg(n) 你已经知道了，但至于你的作业问题，只要你解释你是如何得到解决方案的，你应该没问题。

于 2009-10-06T18:01:06.873 回答