Big O - O（N^2）or O（N^2 + 1）？

Question

我在阅读this Big O文章（以及其他书籍参考）试图找出哪些更改会影响我的算法。

所以给出的以下O（N^2）代码：

bool ContainsDuplicates(String[] strings) 
{ 
    for(int i = 0; i < strings.Length; i++) 
    { 
     for(int j = 0; j < strings.Length; j++) 
     { 
      if(i == j) // Don't compare with self 
      { 
       continue; 
      } 

      if(strings[i] == strings[j]) 
      { 
       return true; 
      } 
     } 
    } 
    return false; 
} 

我作了如下改变：

bool ContainsDuplicates(String[] strings) 
{ 
    for(int i = 0; i < strings.Length; i++) 
    { 
     for(int j = 0; j < strings.Length; j++) 
     { 
      if(i != j) // Don't compare with self 
      {        

        if(strings[i] == strings[j]) 
        { 
         return true; 
        } 
      } 
     } 
    } 
    return false; 
} 

现在两个IF的嵌套和 '继续' 被去除。这个算法是否真的变成了O（N^2 + 1）？为什么？ 据我所知，IF检查之前是否存在，所以最初认为它仍然是一个O（N^2）。

Answer 1

Big O正在描述随着所选参数变大，执行时间如何增长。

在您的例子，如果我们想要准确的说，该公式将是：

所用时间=时间（开始）+时间（外环）* N +时间（继续）* N +时间（无继续）* N^2

哪个可被重写为

采取时间= A + b * N + C * N^2

现在，随着N变得越来越大，很明显整体上它将形成抛物线。随着N增长到无穷大，零阶和一阶项变得无关紧要。

时间采取（大N）〜= C * N^2

最后，因为我们感兴趣的是在讨论定性和不定量，我们简单地描述algorirhm如N^2

O（N^2）意味着该算法将表现大约为c * N^2对于N

0大的值

它与微积分中的o（x）类似的概念（不同之处在于小-o用于参数变为零。