为评估KMP算法的效率，11.3.7节引入一个随迭代过程严格单调递增的观察量k=2i-j，从而简捷地证明了迭代的次数不可能超过o（n)。这一初等的证明虽无可辩驳，但毕竟未能直观地展示出其与计算成本之间的本质联系。试证明，在算法执行的整个过程中：①观察量i始终等于已经做过的成功比对（含与最左端虚拟通配符的“比对”)次数;②观察量i-j始终不小于已经做过的失败比对次数。

查看答案

如果结果不匹配，请联系老师获取答案

您可能会需要：

重置密码查看订单联系客服

更多“为评估KMP算法的效率，11.3.7节引入一个随迭代过程严格…”相关的问题

第1题

KMP算法通过模式串的前缀函数,较好地利用了搜索过程中的部分匹配信息,从而提高了效率.然而在某

些情况下,还可以更好地利用部分匹配信息.例如,考察图9-2中,KMP算法对主串aabaaaab和模式串aaaab的搜索过程.

在图9-2(a)中匹配失败后,按前缀函数指示继续作了图(b)~(d)的比较后,最后在图(e)找到一个匹配.事实上,图(b)~(d)的比较都是多余的.因为模式串在位置0、1、2处的字符和位置3处的字符都相等,因此不需要再和主串中位置3处的字符比较,而可以将模式一次向右滑动4个字符,直接进入图(e)的比较.这就是说,在KMP算法中遇到p[j+1]≠t[i],且p[j+1]=p[next[j]+1]时,可一次向右滑动j-next[next[j]]个字符,而不是j-next[j]个字符.根据此观察,设计一个改进的前缀函数,使得遇到上述特殊情况时效率更高.

点击查看答案

第2题

教材63页代码2.29中的二路归并算法merge（)，反复地通过new和delete操作申请和释放辅助空间。然而实验统计表明，这类操作的实际时间成本，大约是常规运算的100倍，故往往成为制约效率提高的瓶颈。试改写该算法，通过尽量减少此类操作，进一步优化整体效率;

点击查看答案

第3题

二路归并算法merge（)中的循环体，虽然形式上简洁，但流程控制逻辑却较为复杂。a)试分情况验证并解释该算法的正确性;b)基于以上理解，该循环体可以如何简化？c)如果从代码可维护性及运行效率的角度出发，该算法应该如何实现？

点击查看答案

第4题

对于几乎有序的向量，如教材代码2.26（60页)和代码2.27（60页)所示的起泡排序算法，都显得效率不足

对于几乎有序的向量，如教材代码2.26(60页)和代码2.27(60页)所示的起泡排序算法，都显得效率不足，比如，即便乱序元素仅限于A[0，√n)区间，最坏情况下仍需调用bubble()做Ω(√n)次调用，共做Ω(n)次交换操作和Ω(n^3/2)次比较操作，因此累计运行Ω(n^3/2)时间。

a)试改进原算法，使之在上述情况下仅需o(n)时间;

b)继续改进，使之在如下情况下仅需o(n)时间：乱序元素仅限于A[n-√n，n)区间;

c)综合以上改进，使之在如下情况下仅需o(n)时间：乱序元素仅限于任意的A[m，m+√n]区间。

点击查看答案

第5题

【多选题】新冠肺炎患者俯卧位通气前，评估及准备的内容包括（）。

A.评估胃潴留情况，提前暂停胃肠泵入

B.清理口鼻腔及呼吸道分泌物

C.断开不必要的静脉通路，固定好引流管

D.做好受压部位皮肤的保护

点击查看答案

第6题

教材2.6节针对有序向量介绍的各种查找算法，落实减而治之策略的形式均大同小异，反复地“猜测”某

一元素S[mi]，并通过将目标元素与之比较的结果，确定查找范围收缩的方向，然而在某些特殊的场合，沿前、后两个方向深入的代价并不对称，甚至其中之一只允许常数次。

比如，在仅能使用直尺的情况下，可通过反复实验，用鸡蛋刚能摔碎的下落高度(比如精确到毫米)来度量蛋壳的硬度。尽管可以假定在破裂之前蛋壳的硬度保持不变，但毕竟破裂是不可逆的。故若仅有一枚鸡蛋，则我们不得不从0开始，以1毫米为单位逐步增加下落的高度，若蛋壳的硬度不超过n毫米，则需要进行o(n)次实验。就效率而言，这等价于退化到无序向量的顺序查找。

a)若你拥有两枚鸡蛋(假定它们硬度完全相同)，所需实验可减少到多少次？试给出对应的算法;

b)进一步地，如果你拥有三枚鸡蛋呢？

c)一般地，如果共有d枚鸡蛋可用呢？

点击查看答案

第7题

社区口腔卫生服务评估的内容包括

A、适宜程度，足够程度，进度，效率

B、足够程度，进度，效率，效果，影响

C、足够程度，进度，效率，效果

D、效果，效率，适当，适合，成本分析

E、适宜度，足够度，进度，效率，效果，影响

点击查看答案