重复检查功能的大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

回答

相关问题