我的大O是什么?

是的,在我看来是O(N)-从第一个到第二个,从第二个到第三个,输入量增加了10倍,花费了10倍的时间。

特别是,您可以通过以下方法预测大致时间:

f(n) = n / 12500

或

f(n) = n * 0.00008

它对所提供的数据给出了O(N)的最简单解释。

编辑:但是…正如已经指出的那样,数据可能会以各种方式误导您——我更喜欢丹尼斯·帕尔默的观点,即IO成本使其他一切相形见绌。例如,假设您有一个算法,其绝对操作数为:

f(n) = 1000000000000n + (n^2)

在这种情况下,复杂性仍然是O(n^2),但在n非常大之前,从观测结果来看,这种复杂性不会变得明显。

我认为这样说是准确的 这些观察结果暗示了O(N)算法 但这并不意味着绝对是。

看起来是这样,但实际上,您确实需要分析算法,因为根据数据可能会有不同的情况。例如,有些算法对预先排序的数据做得更好或更差。你的算法是什么?

时间行为不是这样的。你所能说的是,这三个数据集彼此之间大致是O(N)。这并不意味着算法是O(n)。

第一个问题是,我可以很容易地画出一条指数曲线(o(e**n)),尽管它包含了这三个点。

不过,最大的问题是你对数据什么都没说。对于排序或接近排序的输入(例如:mergesort),有许多排序算法接近O(N)。然而,它们的平均情况(通常是随机排序的数据)和最坏情况(通常是反向排序的数据)总是O(nlogn)或更糟。

你看不出来。

首先,时间取决于数据、环境和算法。如果您有一个零数组并尝试对其进行排序,那么对于1000或1000000个元素,程序运行时间应该不会有太大的不同。

第二,o表示法告诉我们从n0开始的n的大值的函数行为。可能是您的算法能够很好地扩展到特定的输入大小,然后它的行为会发生变化——比如g(n)函数。

在我看来是O(N)。

是的,这是O(N),因为它与项目数量成比例。

1000000 = 10 * 100000

和

82s = 10 * 8s (roughly)

你不能靠这个说它是O(N)。例如,BubbleSort可以分N步完成,但它是一个O(n^2)算法。

是的,它看起来是O(N),但我认为您不能基于它的定时性能来最终分析该算法。您可能使用了效率最低的排序算法,但有O(N)个定时结果,因为数据读/写时间占总执行时间的大部分。

编辑: big-o取决于算法的效率和它的伸缩性。它应该预测执行时间随着输入项数量的增长而增长。反过来不一定正确。观察给定的执行时间增长可能意味着一些不同的事情。如果它与您给出的示例数字保持一致,那么您可以得出这样的结论:您的程序运行在O(n),但正如其他人所说,这并不意味着您的排序算法是O(n)。