题目内容
（请给出正确答案）
[主观题]
试证明，伸展树所有基本操作接口的分摊时间复杂度，均为o（logn)。
答案
查看答案
重要提示：请勿将账号共享给其他人使用，违者账号将被封禁！
查看《购买须知》>>>
请输入或粘贴题目内容
搜题
拍照、语音搜题，请扫码进入小程序
题目内容
（请给出正确答案）
答案
更多“试证明，伸展树所有基本操作接口的分摊时间复杂度，均为o（logn)。”相关的问题
第2题
A.将来出现的状况
B.将来
C.物理学中的七个基本物理量之一
D.钟表题目来源：智慧树网课批判性思维知到app章节测验答案题库
第3题
关于kd-树查找算法kdSearch()(教244页算法8.2)，试证明以下结论：
a)在树中某一节点发生递归，当且仅当与该节点对应的子区域，与查询区域的边界相交;
b)若令Q(n)=规模为n的子树中与查询区域边界相交的子区域(节点)总数，则有：Q(n)=2+2Q(n/4)=o(√n)。
c)kdSearch()的运行时间为：o(r+√n)，其中r为实际命中并被报告的点数。
d)进一步地，试举例说明，单次查询中的确可能有多达Ω(√n)个节点发生递归，故以上估计是紧的。
e)若矩形区域不保证与坐标轴平行，甚至不是矩形(比如圆)，则上述结论是否依然成立？
第6题
a)任意字符比对的成功与失败概率分别为1/s和(s-1)/s，其中s=|∑|为字符表的规模;
b)在P与T的每一对齐位置，需连续执行恰好k次字符比对操作的概率为(s-1)/sk;
c)在P与T的每一对齐位置，需连续执行字符比对操作的期望次数不超过s/(s-1)≤2=o(1)。
第10题
