noj*_*ojo 17
看起来像,但实际上,你真的需要分析算法,因为根据数据可能会有不同的情况.例如,一些算法对预先排序的数据做得更好或更差.你的算法是什么？
Jon*_*eet 10
是的,对我来说看起来像是O(n) - 从第1个案例到第2个案例,从第2个案例到第3个案例,你已经把输入变大了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))的曲线,但仍包括这三点.
但最大的问题是你没有对数据说什么.有许多排序算法接近O(n)的排序或近似排序的输入(例如:Mergesort).然而,它们的平均情况(通常是随机排序的数据)和最坏情况(通常是反向排序的数据)总是O(nlogn)或更糟.