《算法技术手册》一3.6.2 分治

简介: 本节书摘来华章计算机《算法技术手册》一书中的第3章 ,第3.6.2节, George T.Heineman Gary Pollice Stanley Selkow 著 杨晨 曹如进 译 译更多章节内容可以访问云栖社区“华章计算机”公众号查看。

3.6.2 分治

分治通常是将一个规模为n的问题划分成两个独立的子问题,其中每个子问题的规模约为n/2。大部分时候分治策略是递归形式的,并且会有简单易懂的基本条件用于结束递归。此外,在计算出两个较小问题的解之后,还必须要有一些计算来根据子问题的解计算出原问题的解。
下面来看一个例子:求包含n个数的数组中的最大元素。例3-2展示了如何将原问题分解成两个子问题并通过递归求解。通常,最大值一般是两个子集各自的最大值中比较大的那一个。仔细观察尾递归触发的条件,即子集中只有一个元素vals[left]返回。
例3-2:递归分治求数组中最大值
/* 开始使用递归函数 /
public static int maxElement(int[] vals) {
if (vals.length == 0) {

throw new NoSuchElementException("No Max Element in Empty Array.");

}
return maxElement(vals, 0, vals.length);
}

/** 计算vals[left, right)的最大元素

  • 注意vals[right]并不在计算之列 */
  1. int maxElement(int[] vals, int left, int right) {

if (right - left == 1) {

return vals[left];

}

// 计算子问题
int mid = (left + right) / 2;
int max1 = maxElement(vals, left, mid);
int max2 = maxElement(vals, mid, right);

// 合并处理:从子问题的解中得到当前问题的解
if (max1 > max2) { return max1; }
return max2;
}
例3-2中分治算法的时间复杂度是O(n),因为子问题解的合并处理在常数时间内就能完成。如果这一步需要O(n)时间,那么整体的时间复杂度将会上升至O(n log n)。当然,我们也可以不用分治算法,直接遍历数组并且记下当前所找到的最大值。所以,就当是一个小小的提示吧:分治算法并不总是最快的。

相关文章
|
5天前
|
SQL 存储 算法
【MySQL技术内幕】6.4-锁的算法
【MySQL技术内幕】6.4-锁的算法
21 1
|
5天前
|
存储 算法 关系型数据库
【MySQL技术内幕】5.7- InnoDB存储引擎中的哈希算法
【MySQL技术内幕】5.7- InnoDB存储引擎中的哈希算法
12 1
|
5天前
|
算法 C++
计算机算法设计与分析 第2章 递归与分治策略 (笔记)
计算机算法设计与分析 第2章 递归与分治策略 (笔记)
|
7天前
|
算法 C语言 Ruby
分形逃逸时间算法中的 Normalized Iteration Count(NIC)技术 让颜色更柔和
Normalized Iteration Count (NIC) 技术是一种提升逃逸时间算法中分形图像质量的方法,它产生更平滑的颜色过渡。数学公式表示为:`mu = n + 1 - log(log(|Z(n)|)) / log(p)`,其中 `Z(n)` 是迭代次数,`|Z(n)|` 是复数模长,`p` 通常取2。示例代码提供了 Ruby, Maxima 和 C 语言的实现。
|
9天前
|
存储 自然语言处理 算法
编辑距离算法全解析:优化文本处理的关键技术
编辑距离算法全解析:优化文本处理的关键技术
|
9天前
|
存储 算法 数据挖掘
python5种算法模拟螺旋、分层填充、递归、迭代、分治实现螺旋矩阵ll【力扣题59】
python5种算法模拟螺旋、分层填充、递归、迭代、分治实现螺旋矩阵ll【力扣题59】
|
12天前
|
存储 运维 算法
社交软件红包技术解密(十三):微信团队首次揭秘微信红包算法,为何你抢到的是0.01元
本文中,我们将介绍几种主流的IM红包分配算法,相信聪明的你一定能从中窥见微信红包技术实现的一些奥秘。
13 0
|
14天前
|
算法 NoSQL Python
开山之作!Python数据与算法分析手册,登顶GitHub!
若把编写代码比作行军打仗,那么要想称霸沙场,不能仅靠手中的利刃,还需深谙兵法。 Python是一把利刃,数据结构与算法则是兵法。只有熟读兵法,才能使利刃所向披靡。只有洞彻数据结构与算法,才能真正精通Python。
|
15天前
|
存储 人工智能 算法
RAG技术的高级应用和算法
文章主要探讨了RAG技术的高级应用和算法,系统化地整理了各种方法。
|
15天前
|
机器学习/深度学习 数据采集 算法
基于机器学习的推荐算法构建技术详解
【6月更文挑战第4天】本文详述了构建基于机器学习的推荐算法,特别是协同过滤方法。从用户和物品相似性的角度,解释了用户-用户和物品-物品协同过滤的工作原理。涵盖了数据准备、预处理、特征工程、模型训练、评估优化及结果展示的构建流程。推荐算法在电商、视频和音乐平台广泛应用,未来将受益于大数据和AI技术的进步,提供更智能的推荐服务。

热门文章

最新文章