目前主要有三种方法来求解递回式(至今没有任何一个好的演算法可以有效地解决递回式)
他主要遵循以下三种想法
Example 1. , Θ
我们先猜测大约
先证明基本情况,Θ ,当c足够大时,不等式成立。
接下来证明最多达到,我们将这个表示式展开,对成立,这里不使用Big-O符号作为表示原因在於不能对Big-O符号进行归纳,以下面例子来说:
假设,当n足够大时,n会小於等於常数1,也就是n不会超出常数时间。如果这个为真,那任何演算法都将会是常数时间复杂度,但显然这是错的
基本情况
根据数学归纳法,如果假设
我们可以推出,如果是,1也是
则总和还是,因此由数学归纳法,正确
但这是一个错误的证明,问题点是我们忽略了常数的变化可能会使常数加倍,如果是有限情况下,常数不断加倍仍然是常数,但如果这是一个无穷表示式,常数乘了n倍,那就会出问题了,常数会根据n变化,因此不能被忽略。
为了避免上面这个问题,於是我们将常数写出来,以k做为表示,对成立,我们将展开,,根据我们上面的归纳假设
(小括弧部分为剩余项,是为了化简到)
, 当余项大於或是等於零时
我们证明一下余项必定大於或等於零,如果c为2,则必定大於零成立,如果c为1,则,当n大於1点多时,必成立。
到这里我们证明完毕小於或等於一个常数乘上,这个就是的上界,但其实这不是一个严格的上界,因为也同样会成立。这里所证明的不是的答案就是,而是不会超过这件事情。
我们试着证明
当
,使用上面归纳法的假设将展开
,(小括号的部分式为余项)
,我们必须让余项非负,因为对於递回式来说,只讨论大於等於1的情况
写到这里我们会发现我们无法完成这个归纳法,因此,我们需要修改我们假设
假设当,这里我们改进了我们的归纳法假设,我们之前用的假设是与目前相比较弱的假设,在现在这个假设中,我们把低次项加入进来考虑,先前的假设忽略了常数项与低次项。
我们这里之所以考虑进来低次项,原因是我们期望在解递回式的过程,可以把n给消除掉,只留下,下面开始证明
假设 当
,这里使用了更强的归纳假设,因此需要留下最次低项
中括号部分为余项,同时我们希望余项非负
我们发现当时,余项恒正,因此证明
,当时
接着回头看到基本情况的部分
Θ
我们会发现到,需要大於等於1,那需要足够大,才能满足 Θ,因此整个归纳法的精确结论如下
,当且相对於足够大时
递回树解法,顾名思义是把递回以树的形式展开,虽然直觉,但是相较於代换法没有那麽的严谨,中间递回过程有时候会以...省略,这里需要特别注意,若要求严谨,可以使用代换法去验证递回树,但一般来说不会那麽做。
Example 1.
首先,我们先将这个递回式以树的形式表达,如下图
再将和带入,也就是递回展开的概念。
然後一直不断下去,直到最後,我们会得到一堆叶节点,为Θ。
这里我们可以注意到一件事情,左子树和右子树的递回展开速度是不一样的,会导致两子树的高度不同,我们会难以计算叶子的数量,但我们能够确定一件事情,就是叶子的数量一定会少於n,一开始问题的规模为n,每一次递回会减少1/4,因此当递回结束於,叶的数量必定会少於n,我们试着把这个树每一层的结果加总
我们会发现每一层都会相差,我们把加总,也就是求这个等比级数的何
我们知道上面这个公式计算之後,我们会得到某个常数,我们以c为代表,整个等比级数的何为
,且,以Ω表示
而这个方法不严谨的地方在於等比级数得假设,我们只验证了前三项就认定他是等比级数。下面会介绍基於递回树的更严谨的方法,称为主定理(master theorem)。
主定理有一个限制,那就是只能使用到特定的递回式上面,这些递回式需要符合这样的形式,有a个相同的子问题,每个子问题的规模皆相同,不同於上一个例题,有两个不同规模的子问题。
还有一些限制条件,a需要大於或是等於1,也就是至少要递回一次,b需要严格大於1,因为我们必须让子问题的规模越来越小,f(n)需要趋近於正(asymptotically positive),也就是当n足够大时,必须为正,以数学式表示,即为存在某一个点,当时,
主定理是基於将非递回函数和进行比较,而比较的过程,会出现三种情况,分别为大於,等於,小於,我们可能会直观的想到使用little-o,big-Θ,和smail-ω做为表示,但是,中间会存在一些灰色地带,是我们无法用这些符号进行表示的。
Example 1.
首先,先确认是否符合主定理的限制,
发现符合限制,找到,先确认是属於哪一种情况,也就是先计算
,将代入,得到
我们比较和,发现,也就是,因此属於第一种情况,则结果为,也就是
Example 2.
首先,先确认是否符合主定理的限制,
发现符合限制,找到,先确认是属於哪一种情况,也就是先计算
,将代入,得到
我们比较和,发现,也就是,因此属於第二种情况,则结果为,也就是
Example 3.
首先,先确认是否符合主定理的限制,
发现符合限制,找到,先确认是属於哪一种情况,也就是先计算
,将代入,得到
我们比较和,发现,也就是,因此属於第三种情况,则结果为,也就是
参考资料: Introduciton to algorithms 3rd
大家好我是乌木白!今天要和大家讲 axios 基本语法~ 在处理 AJAX 的时候,有一些套件可以...
链结串列(Linked List)常用来处理相同类型资料,在不连续的记忆体位置,以随机的方式储存,由...
时常为自己排序 这是一个老生常谈的问题了,工作、家庭、财富、人际、健康,什麽对我们来说是最重要的?...
利用 Angualr 框架开发单一应用程序 (Single-Page Application, SP...
1.computed & Watch Part_1 > Lab_Binding >...