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

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


当前回答

为了对被问到的问题保持真诚,我会用回答8岁孩子的方式来回答这个问题

假设一个冰淇淋小贩准备了许多不同形状的冰淇淋(比如N个),按顺序排列。 你想吃中间的冰淇淋

情况1:只有吃完所有比它小的冰淇淋,你才能吃冰淇淋 你将不得不吃掉一半准备好的冰淇淋(输入)。答案直接取决于输入的大小 解是o(N)阶的

情况2:—你可以直接吃中间的冰淇淋

解是O(1)

情况3:只有当你吃完所有比它小的冰淇淋时,你才能吃冰淇淋,每次你吃冰淇淋时,你都允许另一个孩子(每次都是新孩子)吃掉他所有的冰淇淋 总时间为N + N + N.......(N/2)次 溶液是O(N2)

其他回答

为了对被问到的问题保持真诚,我会用回答8岁孩子的方式来回答这个问题

假设一个冰淇淋小贩准备了许多不同形状的冰淇淋(比如N个),按顺序排列。 你想吃中间的冰淇淋

情况1:只有吃完所有比它小的冰淇淋,你才能吃冰淇淋 你将不得不吃掉一半准备好的冰淇淋(输入)。答案直接取决于输入的大小 解是o(N)阶的

情况2:—你可以直接吃中间的冰淇淋

解是O(1)

情况3:只有当你吃完所有比它小的冰淇淋时,你才能吃冰淇淋,每次你吃冰淇淋时,你都允许另一个孩子(每次都是新孩子)吃掉他所有的冰淇淋 总时间为N + N + N.......(N/2)次 溶液是O(N2)

有一件事由于某种原因还没有被提及:

当你看到像O(2^n)或O(n^3)这样的算法时,这通常意味着你将不得不接受一个不完美的问题答案,以获得可接受的性能。

在处理优化问题时,像这样的正确解决方案很常见。在合理的时间内给出一个近乎正确的答案,总比在机器腐烂成灰尘很久之后才给出一个正确答案要好。

以国际象棋为例:我不知道正确的解决方案是什么,但它可能是O(n^50)或更糟。从理论上讲,任何计算机都不可能真正计算出正确答案——即使你用宇宙中的每个粒子作为计算元素,在宇宙生命周期内尽可能短的时间内执行一项操作,你仍然会剩下很多零。(量子计算机能否解决这个问题是另一回事。)

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

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

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

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

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

假设你有一台可以解决一定规模问题的计算机。现在想象一下,我们可以将性能提高几倍。每加倍一次,我们能解决多大的问题?

如果我们能解决一个两倍大的问题,那就是O(n)

如果我们有一个非1的乘数,那就是某种多项式复杂度。例如,如果每加倍一次,问题的规模就会增加约40%,即O(n²),而约30%则是O(n³)。

如果我们只是增加问题的规模,它是指数级的,甚至更糟。例如,如果每翻一倍意味着我们可以解决一个大1的问题,它就是O(2^n)。(这就是为什么使用合理大小的密钥实际上不可能强制使用密码密钥:128位密钥需要的处理量大约是64位密钥的16万亿倍。)

告诉你8年前的log(n)意味着你必须把一个长度为nlog的东西切成两半的次数,让它变成大小为n=1:p

O(nlogn)通常是排序 O(n²)通常是比较所有元素对