《算法设计与分析》——用检索讨论时间复杂度

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了《算法设计与分析》——用检索讨论时间复杂度，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1980字，纯文字阅读大概需要3分钟。

内容图文

检索

• 1. 检索问题
• 2. 顺序检索算法
• • 2.1 最坏情况的时间估计
  • 2.2 平均情况的时间估计
• 3. 改进顺序检索算法
• • 3.1 最坏情况的时间估计
  • 3.2 平均情况的时间估计

1. 检索问题

输入：

(1)升序排列的数组L

(2)元素数n

(3)需要检索的数x

输出：

j

如果x在数组L中，j是x首次出现的下标

否则j=0

基本运算：

x与L中的元素比较

2. 顺序检索算法

j =1, 将 x 与 L [ j ]比较：

如果 x = L [ j ]，则算法停止，输出 j；

如果不等，则把 j 加1，继续 x 与 L [ j ]的比较；

如果 j > n ，则停机并输出0。

实例：

x = 4，需要比较4次；x = 2.5，需要比较5次

2.1 最坏情况的时间估计

不同的输入：

x=L[1], x=L[2], ... , x=L[n]

x< L[1], L[1]< x < L[2], L [2]< x < L[3], ... , x< L [n]

共n+(n+1)个

最坏的输入：

x 不在 L 中或 x = L [ n ] ，要做 n 次比较

最坏情况下时间：

T _max(n)=n

2.2 平均情况的时间估计

输入实例的概率分布：

假设 x 在 L 中概率是 p , 且每个位置概率相等

不在 L 中的概率：1-p

T a v g ( n ) = ∑ i = 1 n   p n i + ( 1 ? p ) n = p n n ( n + 1 ) 2 + ( 1 ? p ) n = p ( n + 1 ) 2 + ( 1 ? p ) n T_{avg}(n)=\displaystyle\sum_{i=1}^{n}\ \frac{p}{n} i+(1-p)n=\frac{p}{n}\frac{n(n+1)}{2}+(1-p)n=\frac{p(n+1)}{2}+(1-p)n Tavg?(n)=i=1∑n? np?i+(1?p)n=np?2n(n+1)?+(1?p)n=2p(n+1)?+(1?p)n

3. 改进顺序检索算法

j =1, 将 x 与L [ j ] (非降顺序排列)比较：

如果 x = L [ j ]，则算法停止，输出 j；

如果 x > L [ j ]，则把 j 加1，继续 x 与 L [ j ]的比较；

如果 x < L [ j ]，则停机并输出0；

如果 j > n ，则停机并输出0.

x = 4，需要比较4次；x = 2.5，需要比较3次

3.1 最坏情况的时间估计

T m a x ( n ) = n T_{max}(n)=n Tmax?(n)=n

3.2 平均情况的时间估计

输入实例的概率分布：

假设 x 在 L 中概率是 p , 且每个位置概率相等，即p/n

不在 L 中的概率：1-p，则每小段的概率为(1-p)/(n+1)

T x ? L ( n ) = T ( x < L 1 ) + T ( L 1 < x < L 2 ) + … … + T ( L n ? 1 < x < L n ) + T ( L n < x ) = 1 + 2 + … … + n + n n + 1 = n 2 + n n + 1 T_{x?L}(n)=T_{(x<L_1)}+T_{(L_1<x<L_2)}+……+T_{(L_{n-1}<x<L_n)}+T_{(Ln<x)}=\frac{1+2+……+n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1} Tx∈/?L?(n)=T(x<L1?)?+T(L1?<x<L2?)?+……+T(Ln?1?<x<Ln?)?+T(Ln<x)?=n+11+2+……+n+n?=2n?+n+1n?

所以：

T a v g = T x ? L ( n ) + T x ∈ L ( n ) = p ( n + 1 ) 2 + n 2 + n n + 1 T_{avg}=T_{x?L}(n)+T_{x∈L}(n)=\frac{p(n+1)}{2}+\frac{n}{2}+\frac{n}{n+1} Tavg?=Tx∈/?L?(n)+Tx∈L?(n)=2p(n+1)?+2n?+n+1n?

内容总结

以上是互联网集市为您收集整理的《算法设计与分析》——用检索讨论时间复杂度全部内容，希望文章能够帮你解决《算法设计与分析》——用检索讨论时间复杂度所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---