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

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

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

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

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

位于L的情况:假设xL的概率为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}

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 六神上课时说了,如果你想成为什么样的人,就去进行深度模仿。个人认为,如果首先不进行深度模仿,可能连为什么成功者...
    5分钟区块链阅读 464评论 1 4
  • 上一章【情感】一遇渣男误终生(2) 可我等的有些心灰意冷了。我是不是做错了,我都做了些什么,李才是自己要找的依靠啊...
    一碗石榴阅读 358评论 0 0
  • 我在好多好多年前就认识你了 所以如老友般的慢慢的过着 秋与冬的凉夜 你的与我的孤寂 我们以为的一直可以走下去 我以...
    梵夜阅读 221评论 0 0
  • 肌肤糖化是怎么回事? 肌肤的衰老,相信各位小姐姐们对“抗氧化”心得颇丰,但对于“糖化”没有什么印象,事实上上,抗糖...
    朱燕春暖花开阅读 357评论 0 0
  • 跨部门之间的沟通,需要彼此的信任感加强,处理好之间的关系更有利于沟通,同时也需要的是部门之间的配合融洽。
    孙倩倩Rela阅读 100评论 0 0