算法分析/比较具有不同增长率的函数的运行时间

Question

我有一个作业问题:

如果一个算法对于 100 的输入大小需要 0.5 毫秒，如果是:

1. 线性，
2. O(N log N),
3. 二次方，
4. 立方体，
5. 指数。

我理解这里的基本概念，我只是不确定如何从数学上解决这个问题。我很想简单地计算处理每个单独的输入项所需的时间(例如，在 a 中)我将 0.5 除以 100 得到 .05，然后乘以 500、1000和 1000 来找出处理这些大小的输入需要多长时间。

虽然这对于线性计算很简单，对于二次和三次计算也非常简单，但我不太明白如何将此策略应用于 (N log N) 或指数函数:我使用什么值作为指数的底数？

对于(N log N)，是不是像计算c = 100 * log(100) = 200那么简单；然后计算 c = 500 * log(500) = 1349，即 6.745 乘以 200，然后将 6.745 乘以 .5 得出 3.3725 作为最终答案？

Answer 1

这是一个糟糕的练习:

• 它教您从单个数据点进行推断。
• 它教您将渐近分析的结果应用到无法应用的地方。

要扩展后者，您无法预测系统在给定特定输入时基于隐藏项的渐近界限的性能。许多算法都隐藏了常量和线性项，这些项在 n=100 等小输入规模的运行时间中占主导地位。

但如果您应该忽略这些事实，那么您的做法是正确的。