我在问更多关于这对我的代码意味着什么。我能从数学上理解这些概念,只是很难理解它们在概念上的含义。例如,如果有人要对一个数据结构执行O(1)操作,我知道它必须执行的操作数量不会增长,因为有更多的项。O(n)操作意味着您将对每个元素执行一组操作。有人能帮我填一下吗?
比如O(n²)的运算会怎样? 如果一个操作是O(nlog (n))这是什么意思? 有人必须吸可卡因才能写出O(x!)吗?
我在问更多关于这对我的代码意味着什么。我能从数学上理解这些概念,只是很难理解它们在概念上的含义。例如,如果有人要对一个数据结构执行O(1)操作,我知道它必须执行的操作数量不会增长,因为有更多的项。O(n)操作意味着您将对每个元素执行一组操作。有人能帮我填一下吗?
比如O(n²)的运算会怎样? 如果一个操作是O(nlog (n))这是什么意思? 有人必须吸可卡因才能写出O(x!)吗?
当前回答
其中很多都很容易用非编程的东西来演示,比如洗牌。
对一副牌进行排序通过遍历整副牌找到黑桃a,然后遍历整副牌找到黑桃2,以此类推最坏情况是n^2,如果这副牌已经倒着排序了。你看了52张牌52次。
一般来说,真正糟糕的算法不一定是故意的,它们通常是对其他东西的误用,比如在同一集合上线性重复的另一个方法中调用一个线性方法。
其他回答
有一件事由于某种原因还没有被提及:
当你看到像O(2^n)或O(n^3)这样的算法时,这通常意味着你将不得不接受一个不完美的问题答案,以获得可接受的性能。
在处理优化问题时,像这样的正确解决方案很常见。在合理的时间内给出一个近乎正确的答案,总比在机器腐烂成灰尘很久之后才给出一个正确答案要好。
以国际象棋为例:我不知道正确的解决方案是什么,但它可能是O(n^50)或更糟。从理论上讲,任何计算机都不可能真正计算出正确答案——即使你用宇宙中的每个粒子作为计算元素,在宇宙生命周期内尽可能短的时间内执行一项操作,你仍然会剩下很多零。(量子计算机能否解决这个问题是另一回事。)
Big-O背后的“直觉
想象一下,当x趋于无穷时,x上的两个函数f(x)和g(x)之间的“竞争”。
现在,如果从某一点开始(某个x点),一个函数的值总是比另一个高,那么我们称这个函数比另一个“快”。
例如,对于每x > 100,你看到f(x) > g(x),那么f(x)比g(x)“快”。
在这种情况下,我们可以说g(x) = O(f(x))F (x)对g(x)提出了某种“速度限制”,因为最终它超过了它,并将其永远甩在后面。
这并不完全是大o符号的定义,它还指出,对于某个常数C, f(x)只需要大于C*g(x)(这只是另一种说法,你不能通过将g(x)乘以常数因子来帮助g(x)赢得竞争- f(x)最终总是会赢)。正式的定义也使用绝对值。但我希望我能让它更直观。
一种思考的方式是:
O(N²)意味着对于每个元素,你都要对其他元素做一些事情,比如比较它们。冒泡排序就是一个例子。
O(N log N)意味着对于每个元素,你只需要看log N个元素。这通常是因为你知道一些元素,可以让你做出有效的选择。最有效的排序就是一个例子,比如归并排序。
O(N!)表示对N个元素的所有可能排列进行处理。旅行推销员就是一个例子,那里有N!访问节点的方法,暴力解决方案是查看每一种可能的排列的总代价,以找到最优的一个。
你可能会发现把它形象化很有用:
同样,在LogY/LogX尺度上,函数n1/2, n, n2都看起来像直线,而在LogY/X尺度上,2n, en, 10n是直线和n!是线性的(看起来像n log n)
big - o符号对代码的重要意义在于,当它所操作的“事物”数量增加一倍时,它将如何扩展。这里有一个具体的例子:
Big-O | computations for 10 things | computations for 100 things ---------------------------------------------------------------------- O(1) | 1 | 1 O(log(n)) | 3 | 7 O(n) | 10 | 100 O(n log(n)) | 30 | 700 O(n^2) | 100 | 10000
快速排序是O(nlog (n))而冒泡排序是O(n²)当排序10个东西时,快速排序比冒泡排序快3倍。但当对100个东西进行排序时,速度要快14倍!显然,选择最快的算法很重要。当您访问具有数百万行的数据库时,这可能意味着您的查询在0.2秒内执行,而不是花费数小时。
另一件需要考虑的事情是,糟糕的算法是摩尔定律无法帮助的事情。例如,如果你有一个O(n^3)的科学计算,它一天可以计算100个东西,处理器速度翻倍一天只能计算125个东西。然而,计算到O(n²),你每天要做1000件事情。
澄清: 实际上,Big-O并没有说不同算法在同一特定大小点上的性能比较,而是说同一算法在不同大小点上的性能比较:
computations computations computations Big-O | for 10 things | for 100 things | for 1000 things ---------------------------------------------------------------------- O(1) | 1 | 1 | 1 O(log(n)) | 1 | 3 | 7 O(n) | 1 | 10 | 100 O(n log(n)) | 1 | 33 | 664 O(n^2) | 1 | 100 | 10000