Ackermann函数A(m,n)可递归定义如下:
试设计一个计算A(m,n)的动态规划算法,该算法只占用O(m)空间(提示:用两个数组val[0:m]和ind[0:m],使得对任何i有val[i]=A(i,ind[i])).
关于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)若矩形区域不保证与坐标轴平行,甚至不是矩形(比如圆),则上述结论是否依然成立?
设f是三元原始递归全函数,g定义为
(1)若h(x)=,(8(x,y))=0),则此时称h为 递归函数是否妥当?为什么?
(2)证明下列函数h是μ-递归函数:
若假定机器字长无限,移位操作只需单位时间,递归不会溢出,且rand()为理想的随机数发生器。试分析以下函数F(n),并以大o记号的形式确定其渐进复杂度的紧上界。
如果在合并排序算法的分割步骤中,将数组a[0:n-1]划分为[ ]个子数组,每个子数组中有O()个元素,然后递归地对分割后的子数组进行排序,最后将所得到的[ ]个排好序的子数组合并成所要求的排好序的数组a[0;n-1].设计一个实现上述策略的合并排序算法,并分析算法的计算复杂性.