我最近试图从clrs中解出一些递推关系,在解这些方程时,我注意到了一个奇怪的细微差别。我不知道你们中是否有人注意到了这一点,也不知道这些理论的拥护者是否能对此给出更多的解释(我也有计算机科学学位,但理论上没有!)。在解主定理的递推时:
t(n)=a t(n/b)+f(n)
我注意到推理过程如下:
i)展开a元递归树,得到每个节点所做工作为(1)的alogb n叶节点,给出所有叶节点的(nlogba)
ii)对于所有非叶节点,g(n)=∑aj f(b/n j),其中j从0到地板(logb n-1)相加,其中树的高度为logb n
iii)现在要有信心:声明f(n)在某些ε>0的情况下,实际上是由O(nlogb a-ε)限定的
iv)现在用f(n)解g(n),用g(n)解t(n)。如第一步所述,T(n)真的是Θ(nlogb a)+g(n),所以一旦有了一些g(n)和另一个术语结合起来,就可以得到T(n)
我用这种方法遇到的麻烦是,这里的推理是这样的:看,如果我们假设右手边是x,那么我们把它插入到方程中来求解左手边。这不是有点奇怪吗?不是这样的吗:
给定:x2=8x-16
所以让我们假设x=4,把它放到rhs中,求x,酷,看,我们得到了4!!!
这确实很有趣,但你真的解决了这个问题-为什么你不把x猜成无理数,为什么不是虚数?
此外,我还想知道,在哪一个数学分支中存在这种推理,因为我怀疑它是从那个领域来到CS的。知道吗?我知道,几乎99%的计算机科学数学只是“在某些假设下的一些更奇特的论点形式”(因为计算机科学专业的学生不在传统意义上解方程),但这种方法似乎还是非常独特的。知道吗?

最佳答案

信心的有趣飞跃是数学归纳的捷径基本上是这样的:
检查某些基本情况(例如,只有一个非叶节点)的假设是否正确。
如果对于nth非基本情况是这样,请确保对于n+1st非基本情况是这样。
你通常可以通过假设你想要证明的是真的,插入它,并显示它是有效的来缩短这个过程在这种情况下,我不太清楚是不是这样。
解决这类问题通常会有一些灵感,因为你必须选择正确的形式来重复,才能使归纳步骤起作用,但这通常不是凭空挑选;在这种情况下,它是从浓密的空气中挑出一些东西,这些空气是由仔细检查叶子节点和其他节点之间的关系而产生的。

关于algorithm - 算法:CLRS的递归关系,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/3615413/

10-09 05:58
查看更多