相关疑难解决方法(0)

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

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

是O(n ^ 2)？

我试图找出使用Big O表示法的for循环的复杂性.我之前在其他课程中已经完成了这个,但是这个比其他课程更严格,因为它是在实际的算法上.代码如下:

for(cnt = 0, i=1; i<=n; i++) //for any size n
{
    for(j = 1; j <= i; j++)
    {
       cnt++;
    }
}

和

for(cnt = 0, i=1; i<=n; i*=2) //for any size n
{
    for(j = 1; j <= i; j++)
    {
       cnt++;
    }
}

我已经到了,第一个循环具有O(n)复杂性,因为它经过n次列表.至于第二个循环,我有点迷失.我相信,对于每个被测试的n,它都会经历一次循环.我(错误地)假设这意味着每次评估循环都是O(n*i).在我的假设中是否有任何我遗漏的东西.我知道cnt ++是恒定的时间.

感谢您在分析中提供的帮助.每个循环都在自己的空间中,它们不在一起.

procedure matrixvector(n:integer);
var i,j:integer;
begin
  for i<-1 to n do begin
    B[i] = 0;
    C[i] = 0;
    for j<-1 to i do 
      B[i]<- B[i]+ A[i,j];
    for j<-n down to i+1 do
      C[i]<-C[i] + A[i,j]
  end
end;

我在确定两组代码示例的Big O运行时间时遇到了一些麻烦,其中迭代依赖于外部循环.我对Big O运行时有一个基本的了解,我可以找出更简单的代码示例的运行时间.我不太确定某些行如何影响运行时间.

我会考虑第一个O(n ^ 2).但是,我不确定.

for(i = 1; i < n; i++){
 for(j = 1000/i; j > 0; j--){  <--Not sure if this is still O(n)
    arr[j]++; /* THIS LINE */
 }
}

我对这个失去了一点点.O(n ^ 3)可能是O(n ^ 2)？

for(i = 0; i < n; i++){
 for(j = i; j < n; j++){
    while( j<n ){
      arr[i] += arr[j]; /* THIS LINE */
      j++;
    }
 }
}

我发现这篇文章并将其应用于第一个代码示例,但我仍然不确定第二个.什么是嵌套循环的Big-O,其中内循环中的迭代次数由外循环的当前迭代确定？

我很好奇使用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++;
  }
}