我有一个整数数组和一些 x 整数值。我需要循环数组比较当前数组值是否等于 x。如果是这样，循环就会中断。
最坏情况的时间复杂度为 W(n) = n(搜索到的元素位于数组末尾)
最好情况的时间复杂度是 B(n) = 1(搜索到的元素位于数组的开头)
我的问题是 - 如何找到这里的平均时间复杂度？
据我所知，有两种可能的情况 - 该元素可以在数组中找到，并且该元素不在那里。但接下来呢？我需要计算一些概率吗？或者只是简单地说 A(n) = n/2？那么第二种情况呢？
最佳答案
元素位于数组中时的平均情况复杂度:
A(n) = n / 2
元素不在数组中时的平均情况复杂度:
A(n) = n
如果该元素在数组中的概率为 0 <= p <= 1 ,
那么你的平均案例复杂度是:
A(n) = p * (n / 2) + (1 - p) * n
关于time-complexity - 求平均时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16984566/