什么是大 O 符号?你使用它吗? [英] What is Big O notation? Do you use it?

问题描述

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

What is Big O notation? Do you use it?

我想我错过了这门大学课程:D

I missed this university class I guess :D

有没有人使用它并举出一些他们使用它的真实例子?

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

八岁儿童的大O?
Big O，你是如何计算/近似的?
您是否在现实生活中应用了计算复杂性理论?

推荐答案

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

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

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

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.

然而，如果你有两种完全不同的算法，一种 (A) 是 O(n^2) 而另一种是 (B>) 是O(log n)，并不是说A比B慢.实际上，对于 100 个项目，A 可能比 B 快十倍.它只是说对于 200 个项目，A 会以 n^2 的倍数增长而 B 会以 的倍数增长得更慢记录 n.因此，如果您对两者进行基准测试并且您知道 A 需要多少时间来处理 100 个项目，以及 B 需要多少时间来处理相同的 100 个项目，并且 A 比 B 快，你可以计算出 B 在多少项上会超过 A 的速度(作为 B 的速度code>B比A下降的慢很多，迟早会超过A——这是肯定的).

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).

这篇关于什么是大 O 符号?你使用它吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！