Is big-O notation a tool to do best, worst, & average case analysis of an algorithm? Or is big-O only for worst case analysis, since it is an upper bounding function?
可以将文章内容翻译成中文,广告屏蔽插件可能会导致该功能失效(如失效，请关闭广告屏蔽插件后再试):
问题:
回答1:
It is Big O, because orders of magnitude are expressed like O(n), O(logN), etc.
The best, worst, and average cases of an algorithm can all be expressed with Big O notation.
For an example of this applied to sorting algorithms, see
http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms
Note that an algorithm can be classified according to multiple, independent criteria such as memory use or CPU use. Often, there is a tradeoff between two or more criteria (e.g. an algorithm that uses little CPU may use quite a bit of memory).
回答2:
Big "O" is a measure of asymptotic complexity, which is to say, roughly how an algorithm scales as N gets really large.
If best & worse converge to the same asymptotic complexity, you can use a single value - or you can figure them out seperately (for example, some sorting algorithms have completely different characteristics on sorted or almost-sorted data than on un-sorted data).
The notation itself doesn't convey this though, how you use it does.
... Or is big-O only for worst case analysis ...
If you give just one asymptotic complexity for an algorithm, it doesn't tell the reader whether (or how) the best and worst case differ from the average.
If you give best-case and worst-case complexity, it tells the reader how they differ.
By default, if a single value is listed, it is probably the average complexity which may (or may not) converge with the worst-case.
