如何通过查看循环来确定Big O性能？

Question

我刚开始学习Big O Notation，老实说我不认为我有这个问题，我不确定如何通过查看循环来确定O（）的性能。我列举了一些例子，然后列出了我认为正确的一些答案！请让我知道，如果他们错了，任何解释将不胜感激！

for (int i = 0; i <1000; i++) { 
     count ++; 

我相信这将是O（n），因为除了定时打印之外，for循环中没有其他任何事情发生。我们迭代'n'次，或者在这种情况下是1000？

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

请问这一个有一个为O（n^2），因为循环嵌套，它遍历ñ两次，N * N？

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

这是另一个O（n^2），但在最坏的情况下？或者这是O（n log n）？

Answer 1

大O符号应该是帮助用户了解运行时如何随输入而增加的指南。

对于第一个示例，无论n是什么，循环都正好运行1000次，因此它是O(1000) = O(1)时间。

对于第二个示例，嵌套循环每次运行外循环时运行n次，运行时间为n次。这是共计n*n = n^2的操作。因此操作次数与n的平方成正比，因此我们说它是O(n^2)。

对于第三个例子，它仍然是O(n^2)。这是因为Big-O符号在时间复杂度的精确公式中忽略了常量。如果您计算j在i增加时运行的次数，则会得到此模式。

i: 0 1 2 3 ... 
j: n n-1 n-2 n-3 ... 

总共操作次数大约在1/2 n^2。由于Big-O符号忽略常量，所以这仍然是O(n^2)