Day-7 Divide-and-Conquer-2 : 求解递回式

如何求解递回式

目前主要有三种方法来求解递回式(至今没有任何一个好的演算法可以有效地解决递回式)

代换法(substitution method)

他主要遵循以下三种想法

  1. 猜大概的答案,例如猜测演算法大约为https://chart.googleapis.com/chart?cht=tx&chl=%7Bcn%7D%5E2
  2. 我们要试着解出常数c,我们会试着验证这个递回式是否成立,使用数学归纳法进行验证。
  3. 找到常数,使问题或是我们的想法可以成立。

Example 1. https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3D4T(n%2F2)%20%2B%20n, https://chart.googleapis.com/chart?cht=tx&chl=T(1)%3DΘhttps://chart.googleapis.com/chart?cht=tx&chl=(1)
我们先猜测大约https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20O(n%5E3)
先证明基本情况,https://chart.googleapis.com/chart?cht=tx&chl=T(1)%20%3D%20Θhttps://chart.googleapis.com/chart?cht=tx&chl=(1) https://chart.googleapis.com/chart?cht=tx&chl=%3C%3D%20%7Bc_1%7D%5E3,当c足够大时,不等式成立。
接下来证明https://chart.googleapis.com/chart?cht=tx&chl=T(n)最多达到https://chart.googleapis.com/chart?cht=tx&chl=%7Bcn%7D%5E3,我们将这个表示式展开,https://chart.googleapis.com/chart?cht=tx&chl=T(k)%3C%3D%7Bck%7D%5E3https://chart.googleapis.com/chart?cht=tx&chl=k%20%3C%3D%20n成立,这里不使用Big-O符号作为表示原因在於不能对Big-O符号进行归纳,以下面例子来说:

假设https://chart.googleapis.com/chart?cht=tx&chl=n%20%3D%20O(1),当n足够大时,n会小於等於常数1,也就是n不会超出常数时间。如果这个为真,那任何演算法都将会是常数时间复杂度,但显然这是错的
基本情况https://chart.googleapis.com/chart?cht=tx&chl=1%20%3D%20O(1)
根据数学归纳法,如果假设https://chart.googleapis.com/chart?cht=tx&chl=n%20-%201%20%3D%20O(1)
我们可以推出https://chart.googleapis.com/chart?cht=tx&chl=n%20%3D%20(n%20-%201)%20%2B%201,如果https://chart.googleapis.com/chart?cht=tx&chl=n%20-%201https://chart.googleapis.com/chart?cht=tx&chl=O(1),1也是https://chart.googleapis.com/chart?cht=tx&chl=O(1)
则总和还是https://chart.googleapis.com/chart?cht=tx&chl=O(1),因此由数学归纳法,https://chart.googleapis.com/chart?cht=tx&chl=n%20%3D%20O(1)正确

但这是一个错误的证明,问题点是我们忽略了常数的变化https://chart.googleapis.com/chart?cht=tx&chl=O(1)%20%2B%20O(1)可能会使常数加倍,如果是有限情况下,常数不断加倍仍然是常数,但如果这是一个无穷表示式,常数乘了n倍,那就会出问题了,常数会根据n变化,因此不能被忽略。

为了避免上面这个问题,於是我们将常数写出来,以k做为表示,https://chart.googleapis.com/chart?cht=tx&chl=T(k)%3C%3D%7Bck%7D%5E3https://chart.googleapis.com/chart?cht=tx&chl=k%20%3C%20n成立,我们将https://chart.googleapis.com/chart?cht=tx&chl=T(n)展开,https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3D4T(%5Cfrac%7Bn%7D%7B2%7D)%20%2B%20n,根据我们上面的归纳假设
https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3D4T(%5Cfrac%7Bn%7D%7B2%7D)%20%2B%20n%20%3C%3D%204c(%5Cfrac%7Bn%7D%7B2%7D)%5E3%20%2B%20n
https://chart.googleapis.com/chart?cht=tx&chl=%3D%20%5Cfrac%7B1%7D%7B2%7Dcn%5E3%2Bn
https://chart.googleapis.com/chart?cht=tx&chl=%3D%20cn%5E3%20-%20(%5Cfrac%7B1%7D%7B2%7Dcn%5E3-n)(小括弧部分为剩余项,是为了化简到https://chart.googleapis.com/chart?cht=tx&chl=cn%5E3)
https://chart.googleapis.com/chart?cht=tx&chl=%3C%3D%20cn%5E3, 当余项大於或是等於零时

我们证明一下余项必定大於或等於零,如果c为2,则https://chart.googleapis.com/chart?cht=tx&chl=n%5E3%20-%20n必定大於零成立,如果c为1,则https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%7B1%7D%7B2%7Dn%5E3%20-%20n,当n大於1点多时,必成立。

到这里我们证明完毕https://chart.googleapis.com/chart?cht=tx&chl=T(n)小於或等於一个常数乘上https://chart.googleapis.com/chart?cht=tx&chl=n%5E3,这个就是https://chart.googleapis.com/chart?cht=tx&chl=T(n)的上界,但其实这不是一个严格的上界,因为https://chart.googleapis.com/chart?cht=tx&chl=n%5E2也同样会成立。这里所证明的不是https://chart.googleapis.com/chart?cht=tx&chl=T(n)的答案就是https://chart.googleapis.com/chart?cht=tx&chl=n%5E3,而是https://chart.googleapis.com/chart?cht=tx&chl=T(n)不会超过https://chart.googleapis.com/chart?cht=tx&chl=n%5E3这件事情。

我们试着证明https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20O(n%5E2)
https://chart.googleapis.com/chart?cht=tx&chl=T(k)%3C%3D%7Bck%7D%5E2https://chart.googleapis.com/chart?cht=tx&chl=k%20%3C%20n
https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%204T(%5Cfrac%7Bn%7D%7B2%7D)%20%2B%20n,使用上面归纳法的假设将https://chart.googleapis.com/chart?cht=tx&chl=T(%5Cfrac%7Bn%7D%7B2%7D)展开
https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%204T(%5Cfrac%7Bn%7D%7B2%7D)%20%2B%20n%20%3C%3D%204c(%5Cfrac%7Bn%7D%7B2%7D)%5E2%20%2B%20n
https://chart.googleapis.com/chart?cht=tx&chl=%7Bcn%7D%5E2%2Bn
https://chart.googleapis.com/chart?cht=tx&chl=%7Bcn%7D%5E2%2B(n),(小括号的部分式为余项)
https://chart.googleapis.com/chart?cht=tx&chl=%7Bcn%7D%5E2-(-n),我们必须让余项非负,因为对於递回式来说,只讨论大於等於1的情况
写到这里我们会发现我们无法完成这个归纳法,因此,我们需要修改我们假设
假设https://chart.googleapis.com/chart?cht=tx&chl=T(k)%20%3C%3D%20%7Bc_1%7Dk%5E2-%7Bc_2%7Dk%20https://chart.googleapis.com/chart?cht=tx&chl=k%20%3C%20n,这里我们改进了我们的归纳法假设,我们之前用的假设是与目前相比较弱的假设,在现在这个假设中,我们把低次项加入进来考虑,先前的假设忽略了常数项与低次项。

我们这里之所以考虑进来低次项,原因是我们期望在解递回式的过程,可以把n给消除掉,只留下https://chart.googleapis.com/chart?cht=tx&chl=%7Bcn%7D%5E2,下面开始证明


https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%204T(%5Cfrac%7Bn%7D%7B2%7D)%20%2B%20n
假设https://chart.googleapis.com/chart?cht=tx&chl=T(k)%20%3C%3D%20%7Bc_1%7Dk%5E2-%7Bc_2%7Dkhttps://chart.googleapis.com/chart?cht=tx&chl=k%20%3C%20n
https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%204T(%5Cfrac%7Bn%7D%7B2%7D)%20%2B%20n%20%3C%3D%204%5Bc_1(%5Cfrac%7Bn%7D%7B2%7D)%5E2-c_2(%5Cfrac%7Bn%7D%7B2%7D)%5D%20%2B%20n
https://chart.googleapis.com/chart?cht=tx&chl=c_1n%5E2%2B(1-2c_2)n,这里使用了更强的归纳假设,因此需要留下最次低项
https://chart.googleapis.com/chart?cht=tx&chl=c_1n%5E2-c_2n%20-%20%5B(-1%2Bc_2)n%5D 中括号部分为余项,同时我们希望余项非负
我们发现当https://chart.googleapis.com/chart?cht=tx&chl=c_2%20%3E%3D%201时,余项恒正,因此证明
https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3C%3D%20c_1n%5E2-c_2n,当https://chart.googleapis.com/chart?cht=tx&chl=c_2%20%3E%3D%201

接着回头看到基本情况的部分
https://chart.googleapis.com/chart?cht=tx&chl=T(1)%20%3C%3D%20c_11%5E2-c_2%2C%20T(1)%20%3D Θhttps://chart.googleapis.com/chart?cht=tx&chl=(1)
我们会发现到,https://chart.googleapis.com/chart?cht=tx&chl=c_2需要大於等於1,那https://chart.googleapis.com/chart?cht=tx&chl=c_1需要足够大,才能满足https://chart.googleapis.com/chart?cht=tx&chl=T(1)%20%3D Θhttps://chart.googleapis.com/chart?cht=tx&chl=(1),因此整个归纳法的精确结论如下
https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3C%3D%20c_1n%5E2-c_2n,当https://chart.googleapis.com/chart?cht=tx&chl=c_2%20%3E%3D%201https://chart.googleapis.com/chart?cht=tx&chl=c_1相对於https://chart.googleapis.com/chart?cht=tx&chl=c_2足够大时

递回树法(recursion-tree method)

递回树解法,顾名思义是把递回以树的形式展开,虽然直觉,但是相较於代换法没有那麽的严谨,中间递回过程有时候会以...省略,这里需要特别注意,若要求严谨,可以使用代换法去验证递回树,但一般来说不会那麽做。

Example 1. https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20T(n%2F4)%20%2B%20T(n%2F2)%20%2B%20n%5E2
首先,我们先将这个递回式以树的形式表达,如下图

再将https://chart.googleapis.com/chart?cht=tx&chl=T(n%2F4)https://chart.googleapis.com/chart?cht=tx&chl=T(n%2F2)带入https://chart.googleapis.com/chart?cht=tx&chl=T(n),也就是递回展开的概念。

然後一直不断下去,直到最後,我们会得到一堆叶节点,为Θhttps://chart.googleapis.com/chart?cht=tx&chl=(1)

这里我们可以注意到一件事情,左子树和右子树的递回展开速度是不一样的,会导致两子树的高度不同,我们会难以计算叶子的数量,但我们能够确定一件事情,就是叶子的数量一定会少於n,一开始问题的规模为n,每一次递回会减少1/4,因此当递回结束於,叶的数量必定会少於n,我们试着把这个树每一层的结果加总

我们会发现每一层都会相差https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%7B5%7D%7B16%7D,我们把加总,也就是求这个等比级数的何
https://chart.googleapis.com/chart?cht=tx&chl=(1%20%2B%20%5Cfrac%7B5%7D%7B16%7D%20%2B%20%5Cfrac%7B25%7D%7B256%7D%20%2B%20...%20%2B%20%5Cfrac%7B5%5Ek%7D%7B16%5Ek%7D%2B...)n%5E2
https://chart.googleapis.com/chart?cht=tx&chl=%5Csum_%7Bi%3D0%7D%5Ek%5Cfrac%7B5%5Ek%7D%7B16%5Ek%7D
我们知道上面这个公式计算之後,我们会得到某个常数,我们以c为代表,整个等比级数的何为
https://chart.googleapis.com/chart?cht=tx&chl=cn%5E2,且https://chart.googleapis.com/chart?cht=tx&chl=cn%5E2%3C2n%5E2,以Ωhttps://chart.googleapis.com/chart?cht=tx&chl=(n%5E2)表示
而这个方法不严谨的地方在於等比级数得假设,我们只验证了前三项就认定他是等比级数。下面会介绍基於递回树的更严谨的方法,称为主定理(master theorem)。

主定理(master theorem)

主定理有一个限制,那就是只能使用到特定的递回式上面,这些递回式需要符合https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3DaT(n%2Fb)%2Bf(n)这样的形式,有a个相同的子问题,每个子问题的规模皆相同,不同於上一个例题,有两个不同规模的子问题。

还有一些限制条件,a需要大於或是等於1,也就是至少要递回一次,b需要严格大於1,因为我们必须让子问题的规模越来越小,f(n)需要趋近於正(asymptotically positive),也就是当n足够大时,https://chart.googleapis.com/chart?cht=tx&chl=f(n)必须为正,以数学式表示,即为存在某一个点https://chart.googleapis.com/chart?cht=tx&chl=n_0,当https://chart.googleapis.com/chart?cht=tx&chl=n%3E%3Dn_0时,https://chart.googleapis.com/chart?cht=tx&chl=f(n)%20%3E%200

主定理是基於将非递回函数https://chart.googleapis.com/chart?cht=tx&chl=f(n)https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blogb%5Ea%7D进行比较,而比较的过程,会出现三种情况,分别为大於,等於,小於,我们可能会直观的想到使用little-o,big-Θ,和smail-ω做为表示,但是,中间会存在一些灰色地带,是我们无法用这些符号进行表示的。

  • 第一种情况,对於εhttps://chart.googleapis.com/chart?cht=tx&chl=%3E0的情况
    https://chart.googleapis.com/chart?cht=tx&chl=f(n)%20%3D%20O(n%5E%7Blogb%5Ea-%5Cvarepsilon%7D),则
    https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(n%5E%7Blogb%5Ea%7D)
  • 第二种情况,对於εhttps://chart.googleapis.com/chart?cht=tx&chl=%3E%3D0
    https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(n%5E%7Blogb%5Ea%7Dlg%5E%7B%5Cvarepsilon%2B1%7Dn),则
    https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(n%5E%7Blogb%5Ea%7Dlg%5E%7B%5Cvarepsilon%2B1%7Dn)
  • 第三种情况,对於εhttps://chart.googleapis.com/chart?cht=tx&chl=%3E0的情况,且需要确保https://chart.googleapis.com/chart?cht=tx&chl=f(n)在递回时不断地变小
    https://chart.googleapis.com/chart?cht=tx&chl=f(n)%20%3D%20%5COmega(n%5E%7Blogb%5E%7Ba%2B%5Cvarepsilon%7D%7D)且对某个常数https://chart.googleapis.com/chart?cht=tx&chl=c%3C1和足够大的n,有https://chart.googleapis.com/chart?cht=tx&chl=af(%5Cfrac%7Bn%7D%7Bb%7D)%3C%3Dcf(n),则
    https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(f(n))

Example 1. https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3D4T(%5Cfrac%7Bn%7D%7B2%7D)%2Bn
首先,先确认是否符合主定理的限制,https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3DaT(n%2Fb)%2Bf(n)
发现符合限制,找到https://chart.googleapis.com/chart?cht=tx&chl=a%20%3D%204%2C%20b%20%3D%202,先确认https://chart.googleapis.com/chart?cht=tx&chl=T(n)是属於哪一种情况,也就是先计算https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea
https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea,将https://chart.googleapis.com/chart?cht=tx&chl=a%20%3D%204%2C%20b%20%3D%202代入,得到
https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7D2%5E4%20%3D%20n%5E2
我们比较https://chart.googleapis.com/chart?cht=tx&chl=f(n)https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea,发现https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea%3Ef(n),也就是https://chart.googleapis.com/chart?cht=tx&chl=f(n)%20%3D%20O(n%5E%7B2-%5Cvarepsilon%7D),因此属於第一种情况,则结果为https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(n%5E%7Blog_b%5Ea%7D),也就是https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(n%5E2)

Example 2. https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3D4T(%5Cfrac%7Bn%7D%7B2%7D)%2Bn%5E2
首先,先确认是否符合主定理的限制,https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3DaT(n%2Fb)%2Bf(n)
发现符合限制,找到https://chart.googleapis.com/chart?cht=tx&chl=a%20%3D%204%2C%20b%20%3D%202,先确认https://chart.googleapis.com/chart?cht=tx&chl=T(n)是属於哪一种情况,也就是先计算https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea
https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea,将https://chart.googleapis.com/chart?cht=tx&chl=a%20%3D%204%2C%20b%20%3D%202代入,得到
https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7D2%5E4%20%3D%20n%5E2
我们比较https://chart.googleapis.com/chart?cht=tx&chl=f(n)https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea,发现https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea%3E%3Df(n),也就是https://chart.googleapis.com/chart?cht=tx&chl=f(n)%20%3D%20%5CTheta(n%5E%7Blogb%5Ea%7Dlg%5E%5Cvarepsilon%20n),因此属於第二种情况,则结果为https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(n%5E%7Blogb%5Ea%7Dlg%5E%7B%5Cvarepsilon%20%2B1%7Dn),也就是https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(n%5E%7B2%7Dlgn)

Example 3. https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3D4T(%5Cfrac%7Bn%7D%7B2%7D)%2Bn%5E3
首先,先确认是否符合主定理的限制,https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3DaT(n%2Fb)%2Bf(n)
发现符合限制,找到https://chart.googleapis.com/chart?cht=tx&chl=a%20%3D%204%2C%20b%20%3D%202,先确认https://chart.googleapis.com/chart?cht=tx&chl=T(n)是属於哪一种情况,也就是先计算https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea
https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea,将https://chart.googleapis.com/chart?cht=tx&chl=a%20%3D%204%2C%20b%20%3D%202代入,得到
https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7D2%5E4%20%3D%20n%5E2
我们比较https://chart.googleapis.com/chart?cht=tx&chl=f(n)https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea,发现https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea%3Cf(n),也就是https://chart.googleapis.com/chart?cht=tx&chl=f(n)%20%3D%20%5COmega(n%5E%7Blogb%5E%7Ba%2B%5Cvarepsilon%7D%7D),因此属於第三种情况,则结果为https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(f(n)),也就是https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(n%5E%7B3%7D)

参考资料: Introduciton to algorithms 3rd


<<:  Day18 认识你的「到达网页」

>>:  Day09表单(HTML)

Day24 axios基本语法(GET、POST请求)?

大家好我是乌木白!今天要和大家讲 axios 基本语法~ 在处理 AJAX 的时候,有一些套件可以...

【Day3】[资料结构]-链结串列Linked List

链结串列(Linked List)常用来处理相同类型资料,在不连续的记忆体位置,以随机的方式储存,由...

2.4.13 Design System - Loading Indicator

时常为自己排序 这是一个老生常谈的问题了,工作、家庭、财富、人际、健康,什麽对我们来说是最重要的?...

第 26 型 - 路由 (Router)

利用 Angualr 框架开发单一应用程序 (Single-Page Application, SP...

Day62 (Vue)

1.computed & Watch Part_1 > Lab_Binding >...