英文:
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)/2，n*(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.
专注分享java语言的经验与见解，让所有开发者获益！
评论