使用 Big O Notation，这个算法的正确标签是什么？

Question

我很好奇。使用 Big-O Notation 来描述这个的正确方法是什么？

var prices = [100, 180, 260, 590, 40, 310, 535, 10, 5, 3];
var biggest_profit = 0;
  
for (var i = 0; i < prices.length; i++) {
    var first_price = prices[i];
  
    for (var j = i + 1; j <= prices.length; j++) {
      // do something here
    }
}

这是让我失望的地方：

j = i + 1

每经过一次i，j就会变得越来越短。

这种模式在大 O 表示法中的正确名称是什么？

Answer 1

如果do something here是一个O(1)操作，整个算法就是O(N^2).

如何计算？（感谢@dfri 错误捕捉）

外循环：i: [0->N-1]

内循环：j: [i+1->N]

总计= N + (N-1) + (N-2) + (N-3) + ... + 1 = N(N+1)/2 = O(N^2)

Answer 2

您可以使用Sigma符号来计算内循环的访问次数("do something here")

其中 (*) 来自 summation rule made famous by the rumour that Gauss once derived it on-the-spot as a young student。

Answer 3

要计算这个算法的大O，想象一个形状：在外部 for 循环的每次迭代中，我们都有一行，由小方块组成。每个方块都是内部 for 循环的一次迭代。因此，对于外部 for 循环的第一次迭代，我们将得到一整行正方形。第二行，将失去一个方块。而第三排，又会少一个。 ... 最后一行只有一个正方形。最后我们会有这个形状：

⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜_____
⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜_______
⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜________
⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜_________
⬜⬜⬜⬜⬜⬜⬜⬜⬜__________
⬜⬜⬜⬜⬜⬜⬜⬜___________
⬜⬜⬜⬜⬜⬜⬜____________
⬜⬜⬜⬜⬜⬜_____________
⬜⬜⬜⬜⬜______________
⬜⬜⬜⬜_______________
⬜⬜⬜________________
⬜⬜_________________
⬜__________________

这是一个大广场的一半。所以它的面积是： prices.length * (prices.length - 1) * 1/2。我们可以删除“-1”，因为它已经足够少了。结果： Prices.length * prices.length * 1/2 1/2 在 Big O 中并不重要。因此该算法具有 O(n^2) 时间复杂度。

Answer 4

var prices = [100, 180, 260, 590, 40, 310, 535, 10, 5, 3];
var biggest_profit = 0;

for (var i = 0; i < prices.length; i++) {  // outer loop
    var first_price = prices[i];

    for (var j = i + 1; j <= prices.length; j++) {  // inner loop
        // do something here
    }
}

在外循环的第一次迭代中（i = 0），内循环执行N次。

在外循环的第二次迭代中（i = 1），内循环执行N - 1次。

在外循环的第三次迭代中（i = 2），内循环执行了N - 2次。

。 . .

在外循环的第N - 2次迭代中（i = N - 3），内循环执行了3次。

在外循环的第N - 1次迭代中（i = N - 2），内循环执行了2次。

在外循环的最后（N次）迭代中（i = N - 1），内循环执行了1次。

因此，这段代码执行的总次数是

N + N - 1 + N - 2 + N - 3 + … + 2 + 1

= 1 + 2 + … + N - 3 + N - 2 + N - 1 + N

代入自然数和公式，

= (N)(N + 1) / 2

= ((N^2) + N) / 2

= O(N^2)，假设 // do something here 在常数时间 O(1) 内执行。

————————

还有，看看这些

使用 Big O Notation，这个算法的正确标签是什么？

Using Big O Notation, what is the correct label for this algorithm?

algorithm

big-o

for-loop

nested

time-complexity