我在问更多关于这对我的代码意味着什么。我能从数学上理解这些概念,只是很难理解它们在概念上的含义。例如,如果有人要对一个数据结构执行O(1)操作,我知道它必须执行的操作数量不会增长,因为有更多的项。O(n)操作意味着您将对每个元素执行一组操作。有人能帮我填一下吗?
比如O(n²)的运算会怎样? 如果一个操作是O(nlog (n))这是什么意思? 有人必须吸可卡因才能写出O(x!)吗?
我在问更多关于这对我的代码意味着什么。我能从数学上理解这些概念,只是很难理解它们在概念上的含义。例如,如果有人要对一个数据结构执行O(1)操作,我知道它必须执行的操作数量不会增长,因为有更多的项。O(n)操作意味着您将对每个元素执行一组操作。有人能帮我填一下吗?
比如O(n²)的运算会怎样? 如果一个操作是O(nlog (n))这是什么意思? 有人必须吸可卡因才能写出O(x!)吗?
当前回答
要理解O(n log n),请记住log n意味着log-base-2 (n)。然后看看每一部分:
O(n)是,当你对集合中的每一项进行操作时。
O(log n)是指操作的次数与取2的指数相同,以得到项目的数量。例如,二分搜索必须将集合切成log n的一半。
O(nlogn)是一个组合——你在对集合中的每一项进行二分搜索。高效的排序通常是对每个项目进行一次循环,并在每个循环中进行良好的搜索,以找到放置相关项目或组的正确位置。因此是n * log n。
其他回答
其中很多都很容易用非编程的东西来演示,比如洗牌。
对一副牌进行排序通过遍历整副牌找到黑桃a,然后遍历整副牌找到黑桃2,以此类推最坏情况是n^2,如果这副牌已经倒着排序了。你看了52张牌52次。
一般来说,真正糟糕的算法不一定是故意的,它们通常是对其他东西的误用,比如在同一集合上线性重复的另一个方法中调用一个线性方法。
我是这样向我那些不懂技术的朋友描述的:
考虑多位数加法。很好的老式铅笔和纸的补充。就是你7-8岁时学的那种。给定两个三位数或四位数,你很容易就能求出它们加起来是多少。
如果我给你两个100位的数字,然后问你它们加起来是多少,即使你必须使用铅笔和纸,计算出来也会非常简单。一个聪明的孩子可以在几分钟内做这样的加法。这只需要大约100次操作。
现在,考虑多位数乘法。你可能在八九岁的时候就学会了。你(希望)做了很多重复的练习来学习它背后的机制。
Now, imagine I gave you those same two 100-digit numbers and told you to multiply them together. This would be a much, much harder task, something that would take you hours to do - and that you'd be unlikely to do without mistakes. The reason for this is that (this version of) multiplication is O(n^2); each digit in the bottom number has to be multiplied by each digit in the top number, leaving a total of about n^2 operations. In the case of the 100-digit numbers, that's 10,000 multiplications.
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
你可能会发现把它形象化很有用:
同样,在LogY/LogX尺度上,函数n1/2, n, n2都看起来像直线,而在LogY/X尺度上,2n, en, 10n是直线和n!是线性的(看起来像n log n)
还记得乌龟和兔子的寓言吗?
从长远来看,乌龟赢了,但从短期来看,兔子赢了。
这就像O(logN)(乌龟)vs O(N)(野兔)。
如果两种方法的大o值不同,那么它们中的一种会在N的水平上获胜,但大o值没有说明N的大小。