我在问更多关于这对我的代码意味着什么。我能从数学上理解这些概念,只是很难理解它们在概念上的含义。例如,如果有人要对一个数据结构执行O(1)操作,我知道它必须执行的操作数量不会增长,因为有更多的项。O(n)操作意味着您将对每个元素执行一组操作。有人能帮我填一下吗?

比如O(n²)的运算会怎样? 如果一个操作是O(nlog (n))这是什么意思? 有人必须吸可卡因才能写出O(x!)吗?


当前回答

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(x!)吗?

不用,用Prolog就行。如果您在Prolog中编写排序算法,只需描述每个元素都应该比前一个元素大,并让回溯为您进行排序,那么它将是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。

还记得乌龟和兔子的寓言吗?

从长远来看,乌龟赢了,但从短期来看,兔子赢了。

这就像O(logN)(乌龟)vs O(N)(野兔)。

如果两种方法的大o值不同,那么它们中的一种会在N的水平上获胜,但大o值没有说明N的大小。

我是这样向我那些不懂技术的朋友描述的:

考虑多位数加法。很好的老式铅笔和纸的补充。就是你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.

把它想象成垂直堆叠乐高积木(n),然后跳过它们。

O(1)表示在每一步,你什么都不做。高度保持不变。

O(n)表示在每一步,你堆叠c块,其中c1是常数。

O(n²)表示在每一步,你堆叠c2 x n个块,其中c2是一个常数,n是堆叠块的数量。

O(nlogn)表示在每一步,你堆叠c3 x n x logn个块,其中c3是一个常数,n是堆叠块的数量。