我的排序值程序时钟在：
- 100000 8s
- 1000000 82s
- 10000000 811s
那是O（n）吗？
问问题
692 次
8 回答
17
看起来是这样，但实际上，你确实需要分析算法，因为根据数据可能会有不同的情况。例如，某些算法对预先排序的数据做得更好或更差。你的算法是什么？
于 2009-11-13T15:33:58.277 回答
10
是的，对我来说，这看起来像 O(n) - 从第 1 种情况到第 2 种情况以及第 2 种情况到第 3 种情况，您已经将输入放大了 10 倍，并且花费了 10 倍的时间。
特别是，您可以使用以下方法预测粗略时间：
f(n) = n / 12500
或者
f(n) = n * 0.00008
它为所提供的数据提供了 O(n) 的最简单解释。
编辑：但是...正如已经指出的那样，数据可能会以多种方式误导您-我更喜欢丹尼斯·帕尔默（Dennis Palmer）的想法，即 IO 成本使其他一切都相形见绌。例如，假设您有一个算法，其绝对操作数为：
f(n) = 1000000000000n + (n^2)
在那种情况下，复杂度仍然是 O(n^2)，但是在 n 非常大之前，这不会从观察中变得明显。
我认为可以准确地说这些观察结果暗示了 O(n) 算法，但这并不意味着它肯定是。
于 2009-11-13T15:32:36.413 回答
8
时间行为并非如此。您真正可以说的是，这三个数据集彼此之间的距离大约为 O(n)。这并不意味着算法是 O(n)。
第一个问题是我可以很容易地绘制一条指数曲线（ O(e**n) ），但它仍然包含这三个点。
但最大的问题是你没有对数据说任何话。对于已排序或接近排序的输入，有许多排序算法接近 O(n)（例如：Mergesort）。然而，它们的平均情况（通常是随机排序的数据）和最坏情况（通常是反向排序的数据）总是 O(nlogn) 或更糟。
于 2009-11-13T15:48:20.700 回答
4
你说不出来。
首先，时间取决于数据、环境和算法。如果您有一个零数组并尝试对其进行排序，那么对于 1000 或 1000000 个元素，程序运行时间应该没有太大差异。
其次，O 表示法讲述了从 n0 开始的较大 n 值的函数行为。可能是您的算法可以很好地扩展到特定的输入大小，然后它的行为会发生变化——比如 g(n) 函数。
于 2009-11-13T16:31:52.763 回答
2
对我来说，它看起来像 O(n)。
于 2009-11-13T15:32:21.480 回答
2
是的，那是 O(n)，因为它与项目的数量成比例。
1000000 = 10 * 100000
和
82s = 10 * 8s (roughly)
于 2009-11-13T15:34:04.960 回答
2
你不能依赖它说它是 O(n)。例如，冒泡排序可以在 n 步内完成，但它是一个 O(n^2) 算法。
于 2009-11-13T16:06:36.263 回答
1
是的，它似乎是 O(n)，但我认为你不能根据算法的定时性能来最终分析算法。您可能正在使用最低效的排序算法，但有 O(n) 时间结果，因为数据读取/写入时间占总执行时间的大部分。
编辑： Big-O 取决于算法的效率及其扩展方式。随着输入项目数量的增加，它应该预测执行时间的增长。反过来不一定是真的。观察执行时间的给定增长可能意味着一些不同的事情。如果它与您给出的示例数字保持一致，那么您可以得出结论，您的程序以 O(n) 运行，但正如其他人所说，这并不意味着您的排序算法是 O(n)。
于 2009-11-13T15:48:49.823 回答