什么是Big O符号?你会用吗?

本文介绍了什么是Big O符号?你会用吗?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

什么是Big O符号?您使用它吗?

我想念这堂大学课:D

有人使用它并提供一些现实生活中使用它的示例吗?

另请参见:

>八岁孩子的Big-O吗? 大O，您如何计算/近似呢? >您是否在现实生活中应用了计算复杂性理论?

解决方案

大多数人在谈论Big-O时忘记了一件重要的事情，因此，我觉得有必要提一下:

您不能使用Big-O比较两种算法的速度. Big-O仅表示如果将处理的项目数量加倍，算法将变慢多少(大约)，或者如果将数量减少一半，则算法变快多少.

但是，如果您有两种完全不同的算法，并且一个(A)是O(n^2)，另一个(B)是O(log n)，则不能说A的速度比.实际上，对于100个项目，A可能比B快十倍.它仅表示，对于200个项目，A的增长速度将降低n^2，而B的增长速度将下降log n倍.因此，如果您对两者进行基准测试，并且知道A处理100个项目需要花费多少时间，并且B对于相同的100个项目需要多少时间，并且A比B更快，则可以计算B的数量将超过速度A的数量(因为B的速度下降的速度比A的速度慢得多，所以迟早会超过A-这是肯定的). /p>

What is Big O notation? Do you use it?

I missed this university class I guess :D

Does anyone use it and give some real life examples of where they used it?

See also:

Big-O for Eight Year Olds? Big O, how do you calculate/approximate it? Did you apply computational complexity theory in real life?

解决方案

One important thing most people forget when talking about Big-O, thus I feel the need to mention that:

You cannot use Big-O to compare the speed of two algorithms. Big-O only says how much slower an algorithm will get (approximately) if you double the number of items processed, or how much faster it will get if you cut the number in half.

However, if you have two entirely different algorithms and one (A) is O(n^2) and the other one (B) is O(log n), it is not said that A is slower than B. Actually, with 100 items, A might be ten times faster than B. It only says that with 200 items, A will grow slower by the factor n^2 and B will grow slower by the factor log n. So, if you benchmark both and you know how much time A takes to process 100 items, and how much time B needs for the same 100 items, and A is faster than B, you can calculate at what amount of items B will overtake A in speed (as the speed of B decreases much slower than the one of A, it will overtake A sooner or later—this is for sure).