我在问更多关于这对我的代码意味着什么。我能从数学上理解这些概念,只是很难理解它们在概念上的含义。例如,如果有人要对一个数据结构执行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)

其他回答

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(N log N)意味着对于每个元素,你只需要看log N个元素。这通常是因为你知道一些元素,可以让你做出有效的选择。最有效的排序就是一个例子,比如归并排序。

O(N!)表示对N个元素的所有可能排列进行处理。旅行推销员就是一个例子,那里有N!访问节点的方法,暴力解决方案是查看每一种可能的排列的总代价,以找到最优的一个。

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

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

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

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

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

Big-O背后的“直觉

想象一下,当x趋于无穷时,x上的两个函数f(x)和g(x)之间的“竞争”。

现在,如果从某一点开始(某个x点),一个函数的值总是比另一个高,那么我们称这个函数比另一个“快”。

例如,对于每x > 100,你看到f(x) > g(x),那么f(x)比g(x)“快”。

在这种情况下,我们可以说g(x) = O(f(x))F (x)对g(x)提出了某种“速度限制”,因为最终它超过了它,并将其永远甩在后面。

这并不完全是大o符号的定义,它还指出,对于某个常数C, f(x)只需要大于C*g(x)(这只是另一种说法,你不能通过将g(x)乘以常数因子来帮助g(x)赢得竞争- f(x)最终总是会赢)。正式的定义也使用绝对值。但我希望我能让它更直观。