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

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

big - o符号对代码的重要意义在于，当它所操作的“事物”数量增加一倍时，它将如何扩展。这里有一个具体的例子:

Big-O       |  computations for 10 things |  computations for 100 things
----------------------------------------------------------------------
O(1)        |   1                         |     1
O(log(n))   |   3                         |     7
O(n)        |  10                         |   100
O(n log(n)) |  30                         |   700
O(n^2)      | 100                         | 10000

快速排序是O(nlog (n))而冒泡排序是O(n²)当排序10个东西时，快速排序比冒泡排序快3倍。但当对100个东西进行排序时，速度要快14倍!显然，选择最快的算法很重要。当您访问具有数百万行的数据库时，这可能意味着您的查询在0.2秒内执行，而不是花费数小时。

另一件需要考虑的事情是，糟糕的算法是摩尔定律无法帮助的事情。例如，如果你有一个O(n^3)的科学计算，它一天可以计算100个东西，处理器速度翻倍一天只能计算125个东西。然而，计算到O(n²)，你每天要做1000件事情。

澄清: 实际上，Big-O并没有说不同算法在同一特定大小点上的性能比较，而是说同一算法在不同大小点上的性能比较:

                 computations     computations       computations
Big-O       |   for 10 things |  for 100 things |  for 1000 things
----------------------------------------------------------------------
O(1)        |        1        |        1        |         1
O(log(n))   |        1        |        3        |         7
O(n)        |        1        |       10        |       100
O(n log(n)) |        1        |       33        |       664
O(n^2)      |        1        |      100        |     10000

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

O(n)表示算法花费的时间随着输入的增加而线性增长。O(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))的算法。(我一时想不起是哪一个了)

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