分而治之算法

这种分治技术是采用高效算法处理各种问题的基础,例如排序(例如快速排序、归并排序)、大数相乘(例如卡拉津巴算法)、寻找最接近的点对、句法分析(例如自上而下的解析器)以及计算离散傅立叶变换(FFT)。

理解和设计分治算法是一项复杂的技能,需要很好地理解所要解决的潜在问题的本质。当用归纳法证明一个定理时,通常需要用一个更一般或更复杂的问题来代替原来的问题,以便初始化递归,并且没有系统的方法去解决所有类似的问题。当用高效的双重递归优化斐波那契数的计算时,可以看到这些分治的复杂情况。

分治算法的正确性通常通过数学归纳法来证明,其计算成本通常通过求解递归关系来确定。

分而治之的范式经常被用来寻找问题的最佳解决方案。它的基本思想是将一个给定的问题分解成两个或更多相似但更简单的子问题,从而依次解决它们,并组合它们的解决方案来解决给定的问题。对于一些足够简单的问题则被直接解决。例如,要对给定的n个自然数列表进行排序,将其分成两个大约各有n/2个自然数的列表,依次对每个列表进行排序,并适当地对两个结果进行交织排序,以获得给定列表的排序版本(见图)。这种方法被称为归并排序算法。

分治法的一个重要应用是在最优化中,其中如果搜索空间在每一步被常数因子压缩(“删减”),整个算法具有与删减步骤相同的渐近复杂性,常数取决于删减因子(通过对几何级数求和);这就是所谓的修剪和搜索。

这些算法的早期例子主要是减治——原始问题被连续地分解成单个子问题,并且确实可以迭代地解决。

分而治之是解决概念性难题的有力工具:它所需要解决的只是将问题分解成子问题、解决琐碎的子问题以及将子问题解决方法结合起来以解决原始问题。同样,减治法需要将问题简化为一个更小的问题,例如经典的汉诺塔难题,它将移动n层塔简化为移动n-1层塔的子问题,并不断重复最终解决原始问题。

分治模式通常有助于发现一些比较高效算法。例如卡拉津巴的快速乘法、快速排序和归并排序算法、应用于矩阵乘法的斯特拉森算法和快速傅立叶变换。

在所有这些例子中,分治方法导致解的渐近成本得到改善。例如,如果(a)基本情况具有特定范围的大小,则分割问题和组合部分解的工作与问题的大小n成比例,当子问题的范围限定数为P时,在每个阶段,子问题的大小为n/p,那么分治算法的成本将是O(nlogpn)。

分治算法一般均适用于在多处理器机器中执行,尤其是共享内存系统,其中处理器之间的数据通信不需要预先计划,因为不同的子问题可以在不同的处理器上执行。

分治算法一般普遍倾向于有效利用内存缓存。原因是一旦一个子问题足够小,原则上它和它的所有子问题都可以在高速缓存中解决,而无需访问运行较慢的主存储器。以这种方式利用高速缓存设计的算法被称为缓存遗忘算法,因为它不将高速缓存大小作为显式参数。此外,分治算法可以被设计用于重要的算法(例如排序、快速傅立叶变换和矩阵乘法),使之成为最佳的高速缓存遗忘算法——无论高速缓存大小如何,它们都渐近意义上以最佳的方式使用高速缓存。相比之下,利用缓存的传统方法是阻塞,如在循环嵌套优化中,问题被明确划分为适当大小的块——这也可以优化使用缓存,但是这种方法仅局限于当算法针对特定机器的特定缓存大小进行调整的情形。

此外,对于其他分层存储系统(如非统一内存访问架构NUMA或虚拟内存)以及多级高速缓存也存在相同的优势。一旦子问题足够小,就可以在给定的分层级别内解决,而无需访问更高(更慢)的级别。

分治算法普遍采用递归实现。在这种情况下,导致当前正在解决的部分子问题会自动存储在过程调用的堆栈中,递归函数是在其定义内调用自身的函数。

分治算法也可以通过非递归程序来实现,该程序将部分子问题存储在一些显式数据结构中,例如堆栈、队列或优先级队列。这种方法允许在选择下一个要解决的子问题时拥有更多的自由度,这在某些应用中很重要,例如在广度优先递归和函数优化的分支定界方法中。这种方法也是一些不支持递归过程的编程语言的标准解决方案。

当使用递归过程时,堆栈溢出可能很难避免,因为许多编译器假设递归堆栈是一个连续的内存区域,有些编译器会为它分配固定数量的空间。编译器在没有被严格要求时,还可以在递归堆栈中保存更多的信息,例如返回地址、不变的参数和过程的内部变量。因此,可以通过使用显式堆栈结构,最小化递归过程的参数和内部变量,从来降低堆栈溢出的风险。

在任何递归算法中,基本情况的选择都有相当大的自由度,这些小的子问题可以直接解决以终止递归。

选择最小或最简单的基本案例,通常会导致程序更简单优雅,因为需要考虑的案例更少,且更容易解决。例如,当输入是单个采样点时,快速傅立叶变换算法可以停止递归,当输入列表为空时,快速排序列表排序算法可以停止递归;在这两个例子中,只需要考虑一个不需要处理的基本情况。

另一方面,当递归在相对较大的案例下停止,并且这些案例难以采用递归解决时效率通常会提高,从而产生混合算法。这种策略避免了递归调用的开销,而递归调用只做很少工作或不做任何工作的,并且还允许使用专门的非递归算法,对于那些基本案例,这些算法比显式递归更有效。简单混合递归算法的一般过程是将基本案例短路,也称为臂长递归。在这种情况下,在函数调用之前检查下一步是否会出现基本案例,以避免不必要的函数调用。例如,在树中递归之前检查null,而不是递归到子节点后再进行检查,这避免了二叉树上某些算法中一半的函数调用。由于分治算法最终将每个问题或子问题实例减少到大量的基本实例,因此这些通常控制算法的总成本,尤其是当分割/连接开销较低时。请注意,这些考虑并不取决于递归是由编译器实现还是由显式堆栈实现。

对于某些问题,分支递归可能会多次评估相同的子问题。在这种情况下,识别和保存这些重叠子问题的解决方案可能是值得的,这种技术通常被称为记忆。一直到极限,它会导致自下而上的分治算法,如动态编程和图表解析。

THE END
1.数的分流(7)——左右课率,正负名之以正负术入之。 正负术曰:今两算得失相反,要令正负以名之。正算赤,负算黑,否则以邪正为异。 方程自有赤、黑相取,法、实数相推求之术。而其并减之势不得广通,故使赤、 黑相消夺之,于算或减或益。 正负的概念,实际上在“盈不足”算法中已经有了雏形,即对盈、朒两势维乘之后,达到不盈不朒的状态,https://zhuanlan.zhihu.com/p/92512462
2.分而治之算法一言以蔽之:分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。 2.分而治之的重点: 看是否能够发现重复的子问题,能否发现大问题存在的循环子结构,如果发现就把原问题转化为很简单的小问题。 是否能划分步骤(不同步骤不同解决方法),因为单个步骤往往比整个https://www.jianshu.com/p/038352946ba3
3.分而治之的算法(DevideandConquer)分而治之的算法(Devide and Conquer) 分治法 分治法是一种一般性的算法设计技术,它将问题的实例划分为若干个较小的实例(最好拥有相同的规模),对这些较小的实例递归求解,然后合并这些解,以得到原始问题的解。许多高效的算法都基于这种技术,虽然有时候它的适应性和效率并不如一些更简单的算法。https://blog.csdn.net/huanghanqian/article/details/78828788
4.基于SmithWaterman算法的并行分而治之生物序列比对算法生物序列比对 动态规划 分而治之 并行处理 内存空间https://www.cnki.com.cn/Article/CJFDTotal-JEXK200402005.htm
5.什么是分率此题中的1/8是分率是小林与小红身高的差去除以小红的身高,1/8是比值,把小红身高数看成单位“1”,“小红比小林矮几分之几”是把小林身高数看成单位“1”,应拿两人身高差去除以小林的身高数,得1/9。这里的 1/9也不是一般分数,而是表示两个数比值的分数。https://xue.baidu.com/okam/pages/strategy-tp/index?strategyId=140962423263312&source=natural
6.经典优化算法之分治法(DivideandConqueAlgorithm)分治分治,即分而治之。分治,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)……直接说就是将一个难以直接https://cloud.tencent.com/developer/article/1523170
7.陈景辉:算法之治:法治的另一种可能性?因此,我的结论将是:算法之治不但不是法治的较优越样态,甚至它都无法被视为真正的法治,它只不过是一种“法制”。尽管它是更先进、更优越、更隐蔽的法制,但它始终还是需要被小心警惕的法制,而不是应当被热情拥抱的法治。 一、法律的算法化:三个规范性理由https://www.legal-theory.org/?mod=info&act=view&id=26587
8.Awesome针对空间,无非就一个办法:大而化小,分而治之(hash映射),你不是说规模太大嘛,那简单啊,就把规模大化为规模小的,各个击破不就完了嘛。 至于所谓的单机及集群问题,通俗点来讲,单机就是处理装载数据的机器有限(只要考虑cpu,内存,硬盘的数据交互),而集群,机器有多辆,适合分布式处理,并https://github.com/Ty-Chen/Awesome-Backend/blob/5ad253a0f2e82d9b83892a60e01a1e0a855d70b3/Data%20Structure%20and%20Algorithm.md
9.2023年中国保险业数字化转型研究报告而此时,领域驱动设计(DDD)作为一种领先的架构设计方法,通过领域实体聚合、限界上下文建模等手段明晰有效的微服务边界,并建立业务架构与技术架构间的映射关系。每个业务领域作为独立的微服务,通过API实现与其他业务的灵活、高效交互。微服务架构与DDD相辅相成,为中台建设提供分而治之的整体思想、精益迭代的演进理念,成为https://36kr.com/p/2382894555673096
10.2022网络治理专题(答题纯享版)*这里我的动词是影响,而不是限制之类完全负面词汇,就是提醒大家,算法并不是造成信息茧房的唯一因素,要时刻谨记辩证思维哈! 算法窄化用户信息获取路径包括两方面:一是信息定制化意味着“自主权”让渡,看与不看看什么由算法决策,从而构建了一个由算法和个人共同决定的拟态环境,平台便通过算法推荐实现算法与商业价值的https://weibo.com/ttarticle/p/show?id=2309404830345634906292
11.算法学习减治·分治·变治51CTO博客经典优化算法之分治法(Divide-and-Conque Algorithm) 转载|【算法】分治法(Divide-and-Conquer Algorithm)经典例子分析 从字面上分析就可以看到有哪些步骤: 分-分解-将问题分解为规模更小的子问题,子问题最好相同或相似; 治-求解-将这些规模更小的子问题逐个击破; https://blog.51cto.com/u_14328065/2884404
12.高一乘杨东︱应对元宇宙挑战:数据安全综合治理三维结构范式多元共治是智能社会治理的题中应有之义,也是破解“治理赤字”的重要法宝。[36]在欧盟的立法模式下,数据被分为个人数据与非个人数据,前者由《通用数据保护条例》(GDPR)保护,而后者由《非个人数据自由流动条例》保护,公共数据纳入基础设施予以保护。然而,个人数据与非个人数据的边界越来越模糊,通过算法分析非个人数据https://www.ccps.gov.cn/bkjd/xzglgg/xgglgg2022_3/202203/t20220325_153412.shtml
13.论坛·DTCC 2022中国数据库技术大会即将召开,120+精选案例抢先看 ·【技术栈公益直播第五十期】人工智能在线下零售智慧门店的技术研究及商业应用落地 ·【在线技术沙龙】开源小秀场系列沙龙活动(第二期) ·求助-天干地支的计算 ·awk数组 ·SDDC之基础架构硬件选型 http://www.chinaunix.net/
14.五大常用算法之一:分治算法分治法是计算机科学中非常重要的算法。字面上的解释是“分而治之”,即将一个复杂的问题分为两个或两个以上相同或相似的子问题,然后将子问题分为更小的子问题。。。直到最后一个子问题可以简单地直接解决,原始问题的解决方案就是子问题的解决方案的结合。这一技能是许多高效算法的基础,如排序算法( 快速排序, 傅https://www.tulingxueyuan.cn/tlzx/jsp/3793.html
15.《中国社会科学文摘》2023年第9期目录价值哲学视域中的算法歧视与社会公正 孙伟平 作者单位:上海大学智能哲学与文化研究院、马克思主义学院,摘自《哲学研究》2023年3期 算法的认识论逻辑 吴畏 作者单位:华中科技大学哲学学院,摘自《哲学动态》2023年3期 数据、平台媒介与公共领域的危机 董山民 作者单位:浙江工商大学马克思主义学院,摘自《广州大学学报》2023年https://cssn.cn/dkzgxp/zgxp_zgshkxwz/2023n/202309/t20230927_5688327.shtml