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

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

作者: w8ed | 来源:发表于2019-03-24 22:25 被阅读0次

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

$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)的公式及示例

本文链接：https://www.haomeiwen.com/subject/ywgpvqtx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

栏目导航

热点阅读

关于我们|服务条款|联系我们|【算法笔记】算法的平均时间复杂度A(n)的公式及示例|投稿指南|网站地图|RSS订阅|排版工具|手机版

提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网版权所有

备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！