试题详情
- 简答题考虑在序列A[1..n]中找最大最小元素的问题。一个分治算法描述如下:如果n≤2就直接求解。否则,将序列等分成两个子序列A[1..n/2]和A[n/2+1..n],分别找出这两子序列的最大最小元素x1,y1和x2,y2;然后据此求出A[1..n]的最大元素x=max{x1,x2}及最小元素y=min{y1,y2}。请给出该算法计算时间T(n)满足的递归方程,并解方程来确定算法的时间复杂度。假定n=2k(k为正整数)。
-
算法时间复杂度满足如下递归方程:
关注下方微信公众号,在线模考后查看
热门试题
- 数据结构与算法里,有下面定义inta[5
- 数据结构与算法里,迭代法与分治法是算法的
- C语言中,定义一维数组intarr[3]
- 就排序记录所在位置而言,希尔排序排序属于
- 数据结构与算法里,可以使用两个下标定义的
- 设某散列表的长度为100,散列函数H(k
- 关于循环嵌套描述不正确的是()
- 下面关于break与continue描述
- 下面关于NP问题说法正确的是()
- 6是完数,其因子包括()
- 已知Ak=(a
- 直接插入排序是不稳定排序而且时间复杂度是
- 在分支限界算法中,根据从活结点表中选择下
- 数据结构与算法里,时间复杂度是O(n*n
- 盘子数量是4的汉诺塔问题,需要移动的步数
- 考虑使用动态规划方法求解下列问题: 01
- 假设有7个物品,它们的重量和价值如下表所
- 查找哈希表,解决冲突的方法包括()。
- 当上下限表达式相等时,我们使用下列哪种表
- 数据结构与算法里,斐波那契数列的第5项的