算法性能说明Ex:O(n)

Question

可能重复:
Big O的简单英文解释

亲爱的大家,

当我阅读有关某些算法的信息时,偶尔会遇到算法性能信息,例如:O(1),O(n),O(n ^ 2)等.

我是否可以获得有关如何翻译和理解这些性能数据的解释？什么样的O(n)变体可用,它们在实践中意味着什么？

谢谢.

Answer 1

你需要一个大O符号的解释.

它衡量算法的复杂程度.由于N倾向于无穷大,所以时间量的方向.

您需要注意的一件事是O(N)乘以常数仍然是O(N).O(2N)确实没有这样的东西.

O(1)表示某事需要一个恒定的时间,即它所花费的时间与您正在处理的数据量无关.

O(N)表示它与您正在处理的数据量成正比,因此如果处理一百万条记录需要一分钟,则需要2分钟才能处理200万条记录.

O(N ^ 2)表示它与N的平方成正比.1000记录需要一分钟,2000需要4分钟,4000需要16分钟等.

您还可以有O(log N)和O(N log N).您可以使用任何基数进行日志,但通常在日志库2中进行测量.因此,一百万条记录将测量为20,因为2 ^ 20接近一百万,而200万条记录将为21.对于N log N,一千条记录将等于10,000,因为1000的日志大约是10,2,000个记录将是22,000,因为2000的日志大约是11.