我在问更多关于这对我的代码意味着什么。我能从数学上理解这些概念，只是很难理解它们在概念上的含义。例如，如果有人要对一个数据结构执行O(1)操作，我知道它必须执行的操作数量不会增长，因为有更多的项。O(n)操作意味着您将对每个元素执行一组操作。有人能帮我填一下吗?
比如O(n²)的运算会怎样? 如果一个操作是O(nlog (n))这是什么意思? 有人必须吸可卡因才能写出O(x!)吗?
当前回答
我是这样向我那些不懂技术的朋友描述的:
考虑多位数加法。很好的老式铅笔和纸的补充。就是你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.
其他回答
我试图用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;
}
}
我喜欢don neufeld的答案，但我想我可以加上O(nlog n)
使用简单分治策略的算法可能是O(log n)最简单的例子是在排序列表中查找某个东西。你不需要从头开始扫描。你走到中间，你决定是向后走还是向前走，跳到中途，直到你找到你要找的东西。
如果您查看快速排序或归并排序算法，您将看到它们都采用将列表分成两半，对每一半排序(使用相同的算法，递归地)，然后重新组合两半的方法。这种递归分治策略是O(nlog n)
If you think about it carefully, you'll see that quicksort does an O(n) partitioning algorithm on the whole n items, then an O(n) partitioning twice on n/2 items, then 4 times on n/4 items, etc... until you get to an n partitions on 1 item (which is degenerate). The number of times you divide n in half to get to 1 is approximately log n, and each step is O(n), so recursive divide and conquer is O(n log n). Mergesort builds the other way, starting with n recombinations of 1 item, and finishing with 1 recombination of n items, where the recombination of two sorted lists is O(n).
至于抽大麻写一个O(n!)算法，除非你别无选择。上面提到的旅行推销员问题被认为是这样一个问题。
把它想象成垂直堆叠乐高积木(n)，然后跳过它们。
O(1)表示在每一步，你什么都不做。高度保持不变。
O(n)表示在每一步，你堆叠c块，其中c1是常数。
O(n²)表示在每一步，你堆叠c2 x n个块，其中c2是一个常数，n是堆叠块的数量。
O(nlogn)表示在每一步，你堆叠c3 x n x logn个块，其中c3是一个常数，n是堆叠块的数量。
你可能会发现把它形象化很有用:
同样，在LogY/LogX尺度上，函数n1/2, n, n2都看起来像直线，而在LogY/X尺度上，2n, en, 10n是直线和n!是线性的(看起来像n log n)
我是这样想的，你有一个任务，要清理一个由坏人V引起的问题，他选择了N，你必须估计出当他增加N时，你需要多长时间来完成你的问题。
O(1) ->增加N并没有什么不同
O(log(N)) ->每次V翻倍N，你必须花费额外的时间T来完成任务。V又翻倍了N，你花了同样多的钱。
O(N) -> V N每翻一倍，花费的时间就翻一倍。
O(N²)- V N每翻一倍，花费的时间就增加4倍。(这不公平!!)
O(nlog (N)) -， V每翻一倍N，你就花两倍的时间，再多一点。
这些是算法的边界;计算机科学家想要描述大n值需要多长时间(当你分解密码学中使用的数字时，这很重要——如果计算机速度提高了10倍，你需要多使用多少位才能确保它们仍然需要100年而不是1年才能破解你的加密?)
有些界限可能有奇怪的表达式，如果它对涉及的人有影响的话。我在Knuth的《计算机编程艺术》中见过类似于O(nlog (N) log(log(N))的算法。(我一时想不起是哪一个了)
