分治法

✍ dations ◷ 2025-04-03 12:57:08 #代数,算法

在计算机科学中,分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

这个技巧是很多高效算法的基础,如排序算法(归并排序、快速排序)、傅立叶变换(快速傅立叶变换)。

另一方面,理解及设计分治法算法的能力需要一定时间去掌握。正如以归纳法去证明一个理论,为了使递归能够推行,很多时候需要用一个较为概括或复杂的问题去取代原有问题。而且并没有一个系统性的方法去适当地概括问题。

分治法这个名称有时亦会用于将问题简化为只有一个细问题的算法,例如用于在已排序的列中查找其中一项的折半搜索算法(或是在数值分析中类似的勘根算法)。这些算法比一般的分治算法更能有效地运行。其中,假如算法使用尾部递归的话,便能转换成简单的循环。但在这广义之下,所有使用递归或循环的算法均被视作“分治算法”。因此,有些作者考虑“分治法”这个名称应只用于每个有最少两个子问题的算法。而只有一个子问题的曾被建议使用减治法这个名称。

分治算法通常以数学归纳法来验证。而它的计算成本则多数以解递归关系式来判定。

折半搜索算法——一个将原来问题连逐地拆细成大约一半大小的单一子问题的分治算法——拥有一段悠长历史。虽然算法在计算机上的清楚描述出现在1946年约翰莫齐利(John Mauchly)的一篇文章里,然而利用已排序的对象序列去加快搜索的构想早已在公元前200年的巴比伦尼亚出现。另一个单一子问题的分治算法是找出2个数的最大公因数的辗转相除法(透过将数字化小至使子问题变得简单),于公元前数世纪已经出现。

一个早期有多个子问题的分治算法是高斯在1805年描述关于快速傅立叶奱换的算法,尽管他没有量化地分析它的操作数目,而快速傅立叶奱换直至在一世纪之后被重新发现之前亦没有广泛流传。这个算法现在称为库利-图基快速傅里叶变换算法。

至于专门用于计算机之上而且正确地分析的分治算法早期例子,则可以数到约翰·冯·诺伊曼于1945年发明的归并排序。

另一个显著的例子是Anatolii Alexeevitch Karatsuba于1960年发明在 O ( n log 2 3 ) {\displaystyle O(n^{\log _{2}3})} 步骤内将两个n位数相乘的Karatsuba算法。它反证了安德雷·柯尔莫哥洛夫于1956年认为这个乘法需要 Ω ( n 2 ) {\displaystyle \Omega (n^{2})} 步骤的猜想。

高德纳举了一个最初并没有涉及计算机的分治算法例子,就是一般邮局用于分发信件的方法:信件在主要邮局根据不同的地理范围而分到不同的袋里,每个袋亦在运送到地区邮局时分到更小的袋里,如是者直至信件被派发为止。这个方法与早于1929年的打孔卡排序机所用的基数排序相类同。

分治算法是一个解决复杂问题的好工具,它可以把问题分解成若干个子问题,把子问题逐个解决,再组合到一起形成大问题的答案。比如,汉诺塔问题如果采用分治算法,可以把高度为n的塔的问题转换成高度为n-1的塔来解决,如此重复,直至问题化简到可以很容易的处理为止。

人们发现有很多效率很高的分治算法,比如,Karatsuba快速乘法算法、快速排序算法和并行算法、矩阵乘法的施特拉森算法、快速傅里叶变换等。

在每一层递归上都有三个步骤:

分治法在高级语言中主要的一个思想是递归,LISP语言中的体现出了极丰富的分治法。

以下是归并排序C语言的示例代码,输入参数中,需要排序的数组为array,起始索引为first,终止索引为last。调用完成后,array中从first到last处于升序排列。

 void merge_sort(int array, unsigned int first, unsigned int last) { 	int mid = 0; 	if(first<last) 	{ 		mid = (first+last)/2; 		merge_sort(array, first, mid); 		merge_sort(array, mid+1,last); 		merge(array,first,mid,last); 	} }

在程序中可以看出分治法的应用:在merge_sort()中,将原来针对索引first到last的数组排序的问题,分为二份较小的问题

最后再进行二个数组的合并。

相关

  • 演化现代生物分类群体从它们的 共同祖先遗传分化的图示。进化论介绍(英语:Introduction to evolution) 演化的证据 共同起源 共同起源的证据群体遗传学 · 遗传多样性 突变 · 自
  • 阿蒙霍特普四世阿蒙霍特普四世(按不同的时间体系估计,去世于前1351年-前1334年之间),后改名埃赫那吞(Akhenaten,亦译做埃赫那顿),古埃及第十八王朝法老。阿蒙霍特普四世是第十八王朝全盛时期的法老
  • 谭献谭献(1832年-1901年),初名廷献,字仲修,号复堂。浙江仁和(今杭州市)人。少时为孤儿,潜心经学,“读书日有程课,凡所论著,隐括于所为日记”。同治六年(1867年)中举。后屡试不第。曾担任福建学
  • 脱氧核糖核酸病毒脱氧核糖核酸病毒(英语:DNA virus),又称DNA病毒,其遗传物质为DNA。一般为正链DNA病毒。医学导航: 病毒病病毒(蛋白质)/分类cutn/syst (hppv/艾滋病, 流感/疱疹/人畜共患)/人名体
  • 安东尼奥·埃加斯·莫尼斯安东尼奥·埃加斯·莫尼斯(António Egas Moniz,1874年11月29日-1955年12月13日),全名António Caetano de Abreu Freire Egas Moniz,葡萄牙精神病学家和神经外科医生。他由于发现
  • 亨利·爱德华·阿姆斯特朗亨利·爱德华·阿姆斯特朗(英语:Henry Edward Armstrong,1848年5月6日-1937年7月13日),英国化学家。阿姆斯特朗在萘衍生物等许多研究领域都十分活跃,但他最为人所知的还是他有关科
  • 吉塔·古达尔吉塔·古达尔(Jetta Goudal,本名朱莉·亨丽特·古德凯,Julie Henriette Goudeket,1891年7月12日-1985年1月14日),荷兰裔美国女演员,成就于好莱坞无声电影时代。吉塔·古达尔出生于18
  • 让二世·德·波旁让二世·德·波旁,第六代波旁公爵 John de Bourbon,6me Duc de Bourbon (1426年-1488年4月1日,又称为好人让或英国人的祸害)法国军人,波旁家族的代表人物之一。波旁公爵及奥弗涅公
  • 哈尼亚乡坐标:57°43′10″N 27°3′9″E / 57.71944°N 27.05250°E / 57.71944; 27.05250哈尼亚乡(爱沙尼亚语:Haanja vald),是爱沙尼亚的一个乡,位于该国东南部,由沃鲁县负责管辖,首府设
  • 飞驒国飞驒国(日语:飛騨国〔飛驒國〕/ひだのくに  */?,“驒”音tuó),日本古代的令制国之一,属东山道,又称飞州。飞驒国的领域大约为现在岐阜县的北部。不明