1

我有一个家庭作业问题：

如果输入大小为 100 的算法需要 0.5 毫秒，那么输入 500、1,000 和 10,000 需要多长时间：

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

我了解这里的基本概念，我只是不确定如何从数学上解决这个问题。我很想简单地计算处理每个输入项所需的时间（例如，在 a 中）我将 0.5 除以 100 得到 0.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 乘以 0.5 得到 3.3725 作为最终答案？

4

2 回答 2

1

这是一个糟糕的练习：

  • 它教您从单个数据点进行推断。
  • 它教你在不能应用的地方应用渐近分析的结果。

为了扩展后者，由于隐藏项，您无法根据渐近界给定特定输入来预测系统的性能。许多算法具有隐藏的常数和线性项，这些项在 n=100 等小输入大小的运行时间中占主导地位。

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

于 2013-10-05T07:16:25.730 回答
0

假设函数的运行时间由 T(n) 给出。您可以通过执行以下操作来解决这些问题：

  1. 假设有一些隐藏的常数乘数，根据函数的增长率写出 T(n) 的一般表达式。例如，对于 n log n 的情况，对于某个常数 c，写为 T(n) = cn log n。

  2. 使用您拥有的一个数据点求解 c；T(100) 给你。

  3. 根据需要插入 n 值以估计运行时间。

这适用于任何增长率。

快速说明：“指数”不够精确，无法做出有意义的估计。2^n 和 100^n 都是指数的，但后者的增长速度明显快于前者。在计算机科学中，通常日志使用以 2 为底的，尽管指数没有通用约定。

希望这可以帮助！

于 2013-10-05T07:14:53.523 回答