我有一个整数数组和一些 x 整数值。我需要遍历数组比较当前数组值是否等于 x。如果是这样，则循环中断。
最坏情况的时间复杂度是 W(n) = n（搜索到的元素在数组的末尾）
最好的情况下的时间复杂度是 B(n) = 1（搜索到的元素在数组的开头）
我的问题是 - 我如何在这里找到平均情况时间复杂度？
据我所知，我有两种可能的情况 - 可以在数组中找到元素，而元素不在其中。但接下来是什么？我必须计算一些概率吗？或者只是简单地说 A(n) = n/2？第二种情况呢？
问问题
6442 次
2 回答
1
此提示希望您使用 Big-O 表示法的可能性非常高（您可以自己查找）。
当元素在数组中或不在数组中时，渐近平均情况复杂度仍然是 O(n)，因为 /2 是从 Big-O 表示法中抽象出来的“常数因子”。
我的猜想得到了进一步证实，因为你没有被告知增加索引或比较两个元素需要多少时间。您已经假设有几件事是“可接受的常量”，因此 /2 此处或此处根本不会改变您所关心的渐近时间复杂度。
于 2013-06-11T21:01:19.003 回答
1
元素在数组中时的平均情况复杂度：
A(n) = n / 2
元素不在数组中时的平均情况复杂度：
A(n) = n
如果元素在数组中的概率为0 <= p <= 1，那么您的平均案例复杂度为：
A(n) = p * (n / 2) + (1 - p) * n
于 2013-06-07T12:51:32.410 回答