我在问更多关于这对我的代码意味着什么。我能从数学上理解这些概念，只是很难理解它们在概念上的含义。例如，如果有人要对一个数据结构执行O(1)操作，我知道它必须执行的操作数量不会增长，因为有更多的项。O(n)操作意味着您将对每个元素执行一组操作。有人能帮我填一下吗?
比如O(n²)的运算会怎样? 如果一个操作是O(nlog (n))这是什么意思? 有人必须吸可卡因才能写出O(x!)吗?
当前回答
把它想象成垂直堆叠乐高积木(n)，然后跳过它们。
O(1)表示在每一步，你什么都不做。高度保持不变。
O(n)表示在每一步，你堆叠c块，其中c1是常数。
O(n²)表示在每一步，你堆叠c2 x n个块，其中c2是一个常数，n是堆叠块的数量。
O(nlogn)表示在每一步，你堆叠c3 x n x logn个块，其中c3是一个常数，n是堆叠块的数量。
其他回答
有一件事由于某种原因还没有被提及:
当你看到像O(2^n)或O(n^3)这样的算法时，这通常意味着你将不得不接受一个不完美的问题答案，以获得可接受的性能。
在处理优化问题时，像这样的正确解决方案很常见。在合理的时间内给出一个近乎正确的答案，总比在机器腐烂成灰尘很久之后才给出一个正确答案要好。
以国际象棋为例:我不知道正确的解决方案是什么，但它可能是O(n^50)或更糟。从理论上讲，任何计算机都不可能真正计算出正确答案——即使你用宇宙中的每个粒子作为计算元素，在宇宙生命周期内尽可能短的时间内执行一项操作，你仍然会剩下很多零。(量子计算机能否解决这个问题是另一回事。)
我试图用c#和JavaScript给出简单的代码示例来解释。
C#
For List<int> numbers = new List<int> {1,2,3,4,5,6,7,12,543,7};
O(1)看起来像
return numbers.First();
O(n)看起来像
int result = 0;
foreach (int num in numbers)
{
result += num;
}
return result;
O(nlog (n))是这样的
int result = 0;
foreach (int num in numbers)
{
int index = numbers.Count - 1;
while (index > 1)
{
// yeah, stupid, but couldn't come up with something more useful :-(
result += numbers[index];
index /= 2;
}
}
return result;
O(n2)是这样的
int result = 0;
foreach (int outerNum in numbers)
{
foreach (int innerNum in numbers)
{
result += outerNum * innerNum;
}
}
return result;
O(n!)看起来，嗯，太累了，想不出任何简单的东西。 但我希望你能明白大意?
JavaScript
对于const数= [1,2,3,4,5,6,7,12,543,7];
O(1)看起来像
numbers[0];
O(n)看起来像
let result = 0;
for (num of numbers){
result += num;
}
O(nlog (n))是这样的
let result = 0;
for (num of numbers){
let index = numbers.length - 1;
while (index > 1){
// yeah, stupid, but couldn't come up with something more useful :-(
result += numbers[index];
index = Math.floor(index/2)
}
}
O(n2)是这样的
let result = 0;
for (outerNum of numbers){
for (innerNum of numbers){
result += outerNum * innerNum;
}
}
你可能会发现把它形象化很有用:
同样，在LogY/LogX尺度上，函数n1/2, n, n2都看起来像直线，而在LogY/X尺度上，2n, en, 10n是直线和n!是线性的(看起来像n log n)
假设你有一台可以解决一定规模问题的计算机。现在想象一下，我们可以将性能提高几倍。每加倍一次，我们能解决多大的问题?
如果我们能解决一个两倍大的问题，那就是O(n)
如果我们有一个非1的乘数，那就是某种多项式复杂度。例如，如果每加倍一次，问题的规模就会增加约40%，即O(n²)，而约30%则是O(n³)。
如果我们只是增加问题的规模，它是指数级的，甚至更糟。例如，如果每翻一倍意味着我们可以解决一个大1的问题，它就是O(2^n)。(这就是为什么使用合理大小的密钥实际上不可能强制使用密码密钥:128位密钥需要的处理量大约是64位密钥的16万亿倍。)
把它想象成垂直堆叠乐高积木(n)，然后跳过它们。
O(1)表示在每一步，你什么都不做。高度保持不变。
O(n)表示在每一步，你堆叠c块，其中c1是常数。
O(n²)表示在每一步，你堆叠c2 x n个块，其中c2是一个常数，n是堆叠块的数量。
O(nlogn)表示在每一步，你堆叠c3 x n x logn个块，其中c3是一个常数，n是堆叠块的数量。
