算法平均时间复杂度计算公式
%20%3D%20%5Csum%5Climits_%7BI%5Cin%20S%7DP_I%20t_I)
其中:
-
是规模为
的实例集
- 实例
的概率为
- 实例的基本运算次数（也就是工作量）为
举例：检索问题，数组
有个元素，每个元素为从1到n的整数。若待检索元素在中（例如1,2,3,4,5），则比较次数为其本身。若待检索元素位于的空隙中（例如0.5,1.5,2.5），则比较次数为，也就是从头到尾比较一遍。若位于和位于的空隙的待检索元素数量各占一半，检索的平均时间复杂度是多少？
位于的情况：假设
在的概率为
，则在每个位置的概率为
，若的值为
，则需要比较次。平均时间复杂度为
位于的空隙的情况：不在的概率为
，每种情况都要比较次，则该情况的平均时间复杂度为n)
综上，结合等差数列求和公式有：
%26%3D%5Csum%5Climits_%7Bi%3D1%7D%5E%7Bn%7D%20i%5Cfrac%7BP%7D%7Bn%7D%2B(1-P)n%20%5C%5C%20%26%3D%5Cfrac%7B(1%2Bn)P%7D%7B2%7D%2B%20(1-P)n%5C%5C%20%5Cend%7Baligned%7D)
当
，
%3D%5Cfrac%7B1%2Bn%7D%7B4%7D%2B%5Cfrac%7Bn%7D%7B2%7D%5Capprox%20%5Cfrac%7B3n%7D%7B4%7D)
