只是为了回应我上面帖子的一些评论:

Domenic - I'm on this site, and I care. Not for pedantry's sake, but because we - as programmers - typically care about precision. Using O( ) notation incorrectly in the style that some have done here renders it kind of meaningless; we may just as well say something takes n^2 units of time as O( n^2 ) under the conventions used here. Using the O( ) adds nothing. It's not just a small discrepancy between common usage and mathematical precision that I'm talking about, it's the difference between it being meaningful and it not.

我知道很多很多优秀的程序员都准确地使用这些术语。说“哦，我们是程序员，所以我们不在乎”会降低整个企业的成本。

一个接一个-嗯，不完全是，尽管我同意你的观点。对于任意大的n，它不是O(1)这是O()的定义。它只是表明O()对于有界n的适用性有限，在这里我们更愿意讨论所走的步数，而不是这个数字的界限。

我会试着为一个真正的八岁男孩写一个解释，除了专业术语和数学概念。

比如O(n²)的运算会怎样?

如果你在一个聚会上，包括你在内有n个人。需要多少次握手才能让每个人都和其他人握手，因为人们可能会在某个时候忘记他们握手的人是谁。

注意:这近似于产生n(n-1)的单形，这足够接近于n²。

如果一个操作是O(nlog (n))这是什么意思?

你最喜欢的球队赢了，他们站在队伍里，队伍里有n名球员。你需要和每个玩家握手多少次，假设你要和每个玩家握手多次，多少次，玩家的号码n中有多少位数字。

注意:这将产生n * log n的10次方。

有人必须吸可卡因才能写出O(x!)吗?

你是一个富二代，你的衣柜里有很多衣服，每种衣服有x个抽屉，抽屉一个挨着一个，第一个抽屉里有一件衣服，每个抽屉里有和左边抽屉一样多的衣服，所以你有一顶帽子，两顶假发，…(x-1)条裤子，然后是x件衬衫。现在，用每个抽屉里的一件物品，你能装扮出多少种风格呢?

注意:这个例子表示一个决策树中有多少个叶结点，其中子结点数=深度，通过1 * 2 * 3 *完成。* x

其中很多都很容易用非编程的东西来演示，比如洗牌。

对一副牌进行排序通过遍历整副牌找到黑桃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.

我试图用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;
    }
}

不，O(n)算法并不意味着它将对每个元素执行操作。大o符号给了你一种方法来谈论你的算法的“速度”独立于你的实际机器。

O(n)表示算法花费的时间随着输入的增加而线性增长。O(n²)意味着你的算法花费的时间是你输入的平方。等等。