重複檢查功能的大O

-1

我想知道如何計算第二秒鐘的大O，而當重複次數持續下降。重複檢查功能的大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; 
}

來源

2017-08-11 Vander Ig

仍然O(n^2)不管較小的重複。

你計算的值是Sum of (n-k) for k = 0 to n.

這相當於(n^2 + n)/2這是自O()忽略常數和次要方面是O(n^2)。

注意您可以通過排序數組O(nlogn)，然後尋找屬於同一O(n)所以總O(nlogn)

來源

2017-08-11 01:32:02 twain249

所以說是正確的，如果在某些時候內循環運行相當於O（n），即使之後運行n-1，...，n-3，.... nk假設外循環運行O（n），內循環仍然是O（n^2）？真正重要的是在最壞的情況下循環運行的時間是多少？ –

同意：「可以通過對數組」O（nlogn）「進行排序來更有效地解決這個問題」然而，這可以更好嗎？嗯。聽起來類似於[生日悖論]（https://en.wikipedia.org/wiki/Birthday_problem） – chux

@VanderIg是大O是最壞的情況下測量。 @Chux也許還有其他的方法比'O（nlogn）'更好，但我不知道任何東西。此外，我認爲生日悖論僅適用於有限數量的選項（366）。 – twain249

大O是一個估計值/理論速度連續兩個數字更有效地解決這個問題，這不是精確的計算。

像twain249說，無論，時間複雜度是O(n^2)

來源

2017-08-11 01:33:49 glyif

戈顯示一個算法，表示最大時間的最壞情況下的時間複雜度的算法可以採取ever.It示出上限這表明無論投入是時間複雜性將永遠在這個界限之下。在你的情況最壞的情況下將當我將迭代，直到0，那麼複雜性將是這樣的：

對於i = NJ將運行N-1次，對於i = N-1Ĵ將運行的n-2次，所以上。（n-1）+（n-2）+（n-3）+ ............（nn）=（n-1）*（n）/ 2 = n的所有（n-1）^2/2-n/2 忽略下一項是n並且常數是1/2，它變成n^2。所以O（n^2）就是這樣計算的。

來源

2017-08-11 02:22:51

重複檢查功能的大O

回答

相關問題