当前位置：文江博客话题详情

使用divide and-conquer; to divide and-conquer＆＃x9; to witr＆＃x9; and algorithm＆＃x9; algorithM＆＃x9; x9;项目

发布于 2025-01-23 03:15:31 字数 63 浏览 3 评论 0原文

使用分界线和争议方法编写一种算法，该算法找到最大的项目
在n个项目列表中。分析您的算法，并按顺序显示结果

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

甜尕妞 2025-01-30 03:15:31

用于在数组中找到最大元素的分裂和诱导算法将阵列分为两半，分别求解每个子问题，然后将解决方案的最大值返回到两个子问题上。递归的基本情况是当子问题具有1尺寸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)}

A divide-and-conquer algorithm for finding the maximum element in an array would split the array into two halves, solve each subproblem separately and return the maximum of the solutions to the two subproblems. The base case of the recursion would be when the subproblem has size 1, in which case the maximum is the element in the array. The recurrence for the running time is $T(n)=2T(n/2)+c$, which has solution $T(n)=\Theta(n)$ by the Master theorem.
This is the same asymptotic running time as (but a constant factor larger than) linear search. Here's the pseudocode:

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)}

回复收藏 0 原文

~没有更多了~