大O表示法用于在数组中查找重复元素的两个嵌套for循环。

huangapple 未分类评论52阅读模式
英文:

Big Oh Notation for 2 nested for loop in finding duplicate element in an array

问题

对于上述嵌套的循环:
第一个循环有 n 次迭代,
第二个循环有 n-1 次迭代。

因此总共进行了 n(n-1) 次迭代。
但实际上是 n(n-1)/2 次。想知道为什么会多出一半的次数。需要帮助。

英文:
for i=1 to n
 for j=i+1 to n
  if A[i]==B[j] return TRUE
return FALSE

Query : in this above nested for loop --> 1st for loop has n iterations
2nd loop has n-1 iterations.

so n(n-1) iterations happens.
But it is actually n(n-1)/2 times. wondering how does it is one more half the times. need help.

答案1

得分: 0

最坏情况下,您嵌套循环算法的时间复杂度为O(n2)

当执行渐近分析时,会忽略较低阶的项和常数因子,因此无论您是否具有 n(n-1)n*(n-1)/2n*(n-5)/6 等表达式,重要的是这些表达式中具有最高阶的是 N2,这就是时间复杂度。

英文:

Worst-case time complexity of your nested loops' algorithm is O(n<sup>2</sup>).

Lower order terms and constant factors are disregarded when the Asymptotic Analysis is performed, so it doesn't matter whether you're having n(n-1), n*(n-1)/2, n*(n-5)/6 or etc. important point is that you're having highest order in these expressions N<sup>2</sup>, and that's the time complexity.

huangapple
  • 本文由 发表于 2020年7月26日 15:47:26
  • 转载请务必保留本文链接:https://java.coder-hub.com/63097466.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定