c - 大O重复检查功能

Question

我想确切地知道当重复次数随着时间的推移不断下降时如何计算第二个大O。

int duplicate_check(int a[], int n) 
     {
      int i = n; 
       while (i > 0) 
       {
          i--; 
          int j = i - 1; 
         while (j >= 0) 
          { 
            if (a[i] == a[j]) 
               { 
                 return 1; 

               } 

           j--; 
          } 
        }
    return 0; 
}

Answer 1

无论重复次数如何，仍然是O(n^2)。

您正在计算的值是k = 0 到 n 的 (n-k) 之和。

这相当于 (n^2 + n)/2，因为 O() 忽略常量和次要项，因此 O(n^2).

请注意，您可以通过对数组进行排序O(nlogn)，然后搜索两个相同O(n)的连续数字来更有效地解决这个问题，所以总共O(nlogn)