使用分而治之的方法来编写一个查找最大项的算法。
使用分而治之的方法来编写一个查找最大项的算法。
提问于 2022-04-20 10:44:22
使用分而治之的方法来编写一个查找最大项的算法。
在n个项目的列表中。分析算法，并以顺序表示法显示结果。
回答 1
Stack Overflow用户
发布于 2022-04-21 02:13:20
一种求数组中最大元素的分而治之算法将数组分成两半，分别求解每个子问题，并将解的最大值返回给两个子问题。递归的基本情况是子问题的大小为1，在这种情况下，最大值是数组中的元素。运行时间的递推为$T(n)=2T(n/2)+c$，其解为$T(n)=\Theta(n)$。这是与线性搜索相同的渐近运行时间(但常数因子大于)。这是伪码：
Function FindMax(A,p,r):
#input: an array A[p..r]. Returns maximum value
if p=r then return A[p] #base case of recursion
else:
q = (p+r)//2 #midpoint
return max{FindMax(A,p,q), FindMax(A,q+1,r)}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/71938291
复制相关文章
相似问题
腾讯云开发者
