使用Big O表示法,此算法的正确标签是什么？

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变得越来越短.

Big O Notation中此模式的正确名称是什么？

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表示法来计算内循环的访问次数("在此处执行操作")

凡(*)从如下由高斯一旦得出它在现场作为一个年轻学生的传闻而闻名求和规则.