Algorithm Performance Explanation Ex: O(n)
Possible Duplicate:
Plain English explanation of Big O
Dear all,
As I read information about some algorithms, occasionally, I encounter algorithm performance information, such as: O(1), O(n), O(n^2) etc..
Could I kindly get explanation on how to translate and understand this performance data? What kind of O(n) variants are available, and what do they mean in practice?
Thank you.
You need an explanation of big-O notation.
It is a measure of the complexity of an algorithm. As N tends to infinity, the direction the amount of time will take.
One thing you need to be aware of is that O(N) multiplied by a constant is still O(N). There is no such thing really as O(2N).
O(1) means something takes a constant time, ie the amount of time it takes is unrelated to the amount of data you are processing.
O(N) means it is proportional to the amount of data you are processing, so if it takes a minute to process a million records, it will take 2 minutes to process 2 million.
O(N^2) means it is proportional to the square of N. 1000 records takes a minute, 2000 takes 4 minutes, 4000 takes 16 minutes, etc.
You can also have O(log N) and O(N log N). You can use any base for log but one commonly measures in log base 2. So a million records would measure as 20 because 2^20 is close to a million, and 2 million records would be 21. For N log N, a thousand records would be equivalent to 10,000 because the log of 1000 is approximately 10. 2 thousand records would be 22,000, as the log of 2000 is approximately 11.
从维基百科开始：http：//en.wikipedia.org/wiki/Big-o_notation。
链接地址: http://www.djcxy.com/p/6762.html上一篇: O符号是什么意思？
下一篇: 算法性能说明例如：O（n）