【算法笔记】算法的平均时间复杂度A(n)的公式及示例

2019-03-24 本文已影响0人 w8ed

算法平均时间复杂度计算公式

$A(n) = \sum\limits_{I\in S}P_I t_I$
其中:

$S$ 是规模为 $n$ 的实例集
实例 $I$ 的概率为 $P_I$
实例 $I$ 的基本运算次数（也就是工作量）为 $t_I$

举例：检索问题，数组 $L$ 有 $n$ 个元素，每个元素为从1到n的整数。若待检索元素在 $L$ 中（例如1,2,3,4,5），则比较次数为其本身。若待检索元素位于 $L$ 的空隙中（例如0.5,1.5,2.5），则比较次数为 $n$ ，也就是从头到尾比较一遍。若位于 $L$ 和位于 $L$ 的空隙的待检索元素数量各占一半，检索的平均时间复杂度是多少？

位于 $L$ 的情况：假设 $x$ 在 $L$ 的概率为 $P$ ，则 $x$ 在每个位置的概率为 $\frac{P}{n}$ ，若 $x$ 的值为 $i$ ，则需要比较 $i$ 次。平均时间复杂度为 $\sum\limits_{i=1}^{n} i\frac{P}{n}$

位于 $L$ 的空隙的情况： $x$ 不在 $L$ 的概率为 $1-P$ ，每种情况都要比较 $n$ 次，则该情况的平均时间复杂度为 $(1-P)n$

综上，结合等差数列求和公式有：
$\begin{aligned} A(n)&=\sum\limits_{i=1}^{n} i\frac{P}{n}+(1-P)n \\ &=\frac{(1+n)P}{2}+ (1-P)n\\ \end{aligned}$

当 $P = \frac{1}{2}$ ，
$A(n)=\frac{1+n}{4}+\frac{n}{2}\approx \frac{3n}{4}$

【算法笔记】算法的平均时间复杂度A(n)的公式及示例

猜你喜欢

热点阅读