分析我的程序的时间复杂性

Question

我在确定算法的时间复杂性方面存在问题.

for(int i=0;i <n i++){}   O(n)

for(int i= 0 ;i<n ;i++){    O(n^2)
  for(int j=0;j<n;j++){ 

  }
}

现在,对于以下代码的复杂性

for(i =0; i<n ; i++) {}
for (j=0;j<n ;j++ ) {}

它是O(2n),因为它开发了2个单独的循环？

如果我开始j = 5到n怎么办？

Answer 1

没有O(2n),只是O(n).换句话说,它以与n增加相同的速率缩放.

如果它是一个嵌套循环,那就是空块的存在意味着它不是嵌套的.O(n²){}

无论你是从一个还是五个开始,它仍然没有差别,它仍然n可以随着一个略微负的恒定加法.因此,仍然O(n).

的复杂性O(n),O(cn)和O(n+c)(其中,c是常数)都是等效的.此外,您通常也只使用效果最高的术语.

所以你通常不会看到,那将简化为.O(7n³ + 3n² + 12n + 2)O(n³)