相关疑难解决方法(0)

大多数拥有CS学位的人肯定会知道Big O代表什么.它可以帮助我们衡量算法的实际效率(如何),如果你知道你试图解决的问题属于哪个类别,你可以弄清楚是否仍然可以挤出那么少的额外性能.¹

但我很好奇,你如何计算或近似算法的复杂性？

¹ _{但正如他们所说,不要过度,过早优化是所有邪恶的根源,没有正当理由的优化也应该得到这个名称.}

以下嵌套循环的Big-O时间复杂度是多少:

for(int i = 0; i < N; i++) 
{
    for(int j = i + 1; j < N; j++)
    {
        System.out.println("i = " + i + " j = " + j);
    }

}

它还是O(N ^ 2)吗？

我需要计算以下代码的时间复杂度:

for (i = 1; i <= n; i++)
{
  for(j = 1; j <= i; j++)
  {
   // Some code
  }
}

是O(n ^ 2)？

我很好奇使用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中此模式的正确名称是什么？

如果以下循环结构处于上限分析中，它是否仍然计算为 O(n^2)？我很困惑，因为内部循环依赖于外部循环，并且每次外部迭代时，内部 for 循环都会少循环一次。除了 O(n) 是什么之外，时间复杂度函数是否会是“n!.n+C”（其中 C 是常数）？我假设n！因为内循环。

for(int i=n;i>0;i--)
{
 for(int j=i;j>=1;j--)
  {
     count++;
  }
}