求解递推关系:T(n)=T(n-1)+T(n/2)+n

Solving a Recurrence Relation: T(n)=T(n-1)+T(n/2)+n

求解:T(n)=T(n-1)+T(n/2)+n.

我尝试使用递归解决这个问题 trees.There 分别是两个分支 T(n-1)T(n/2)T(n-1) 会更深入。所以我们得到 O(2^n)。这个想法对吗?

我相信你是对的。递归关系总是会分裂成两部分,即T(n-1)和T(n/2)。看看这两个,很明显 n-1 的值下降速度比 n/2 慢,或者换句话说,你会从树的 n-1 部分得到更多的分支。尽管如此,在考虑 big-o 时,只考虑 'worst-case' 场景是有用的,在这种情况下,树的两侧都减少了 n-1(因为这减少得更慢,你需要有更多的分支机构)。总之,您需要将关系一分为二 n 次,因此您说 O(2^n).

是对的

对于 CS class,这是一个非常奇怪的重复。这是因为从一个角度来看:T(n) = T(n-1) + T(n/2) + n 大于 T(n) = T(n-1) + n 即 O(n^2).

但是从另一个角度来看,functional equation有一个精确解T(n) = -2(n + 2)。通过将其代回等式,您可以很容易地看出这是精确解:-2(n + 2) = -2(n + 1) + -(n + 2) + n。我不确定这是否是唯一的解决方案。

我是这样得到它的:T(n) = T(n-1) + T(n/2) + n。因为你计算的东西很大 n,所以 n-1n 差不多。所以可以改写成T(n) = T(n) + T(n/2) + n也就是T(n/2) + n = 0,等于T(n) = - 2n,所以是线性的。这对我来说是违反直觉的(这里是减号),但是有了这个解决方案,我尝试了 T(n) = -2n + a 并找到了 a.

的值

T(n)=T(n-1)+T(n/2)+nT(n)=T(n)+T(n/2)+n 相同,因为我们求解的是极大的 n 值。 T(n)=T(n)+T(n/2)+n 仅在 T(n/2) + n = 0 时为真。这意味着 T(n) = T(n) + 0 ~= O(n)

你的推理是正确的,但你放弃的太多了。 (例如,2x^3+4=O(2^n) 也是正确的,但不如 2x^3+4=O(x^3) 提供更多信息。)

我们要做的第一件事就是去掉非齐次项n。这表明我们可以寻找 T(n)=an+b 形式的解决方案。代入其中,我们发现:

an+b = a(n-1)+b + an/2+b + n

减少到

0 = (a/2+1)n + (b-a)

暗示a=-2b=a=-2。因此,T(n)=-2n-2是方程的解。

我们现在想通过减去我们已经找到的解决方案来找到其他解决方案。让我们定义 U(n)=T(n)+2n+2。那么等式就变成了

U(n)-2n-2 = U(n-1)-2(n-1)-2 + U(n/2)-2(n/2)-2 + n

减少到

U(n) = U(n-1) + U(n/2).

U(n)=0 是这个方程的明显解,但是这个方程的非平凡解如何表现?

让我们假设 U(n)∈Θ(n^k) 对于某些 k>0,因此 U(n)=cn^k+o(n^k)。这使得等式

cn^k+o(n^k) = c(n-1)^k+o((n-1)^k) + c(n/2)^k+o((n/2)^k)

现在,(n-1)^k=n^k+Θ(n^{k-1}),这样上面就变成了

cn^k+o(n^k) = cn^k+Θ(cn^{k-1})+o(n^k+Θ(n^{k-1})) + cn^k/2^k+o((n/2)^k)

吸收低阶项并减去公共项cn^k,我们得到

o(n^k) = cn^k/2^k

但这是错误的,因为右边比左边长得快。因此,U(n-1)+U(n/2)U(n) 增长得更快,这意味着 U(n) 必须比我们假设的 Θ(n^k) 增长得更快。因为对于任何 k 都是如此,U(n) 必须比任何多项式增长得更快。

指数函数是比任何多项式增长都快的一个很好的例子。因此,让我们假设 U(n)∈Θ(c^n) 对于某些 c>1,因此 U(n)=ac^n+o(c^n)。这使得等式 ac^n+o(c^n) = ac^{n-1}+o(c^{n-1}) + ac^{n/2}+o(c^{n/2 }) 重新排列并使用某种增长数学顺序,这就变成了

c^n = o(c^n)

这(又)是错误的,因为左边比右边长得快。所以, U(n)U(n-1)+U(n/2) 增长得更快,这意味着 U(n) 必须比我们假设的 Θ(c^n) 增长得慢。由于这对于任何 c>1 都是正确的,U(n) 必须比任何指数增长得更慢。

这将我们带入准多项式领域,其中 ln U(n)∈O(log^c n),以及次指数领域,其中 ln U(n)∈O(n^ε)。这些中的任何一个都意味着我们要查看 L(n):=ln U(n),而前面的段落暗示 L(n)∈ω(ln n)∩o(n)。取方程的自然对数,我们有

ln U(n) = ln( U(n-1) + U(n/2) ) = ln U(n-1) + ln(1+ U(n/2)/U(n-1))

L(n) = L(n-1) + ln( 1 + e^{-L(n-1)+L(n/2)} ) = L(n-1) + e^{-(L(n-1)-L(n/2))} + Θ(e^{-2(L(n-1)-L(n/2))})

所以一切都归结为:L(n-1)-L(n/2) 增长的速度有多快?我们知道 L(n-1)-L(n/2)→∞,否则 L(n)∈Ω(n)。而且 L(n)-L(n/2) 可能同样有用,因为 L(n)-L(n-1)∈o(1)L(n-1)-L(n/2).

小得多

不幸的是,这是我所能解决的问题。我没有找到控制 L(n)-L(n/2) 增长速度的好方法(几个月来我一直盯着这个看)。我唯一可以结束的是引用另一个答案:“CS class 的一个非常奇怪的递归”。

我想我们可以这样看:

T(n)=2T(n/2)+n < T(n)=T(n−1)+T(n/2)+n < T(n)=2T(n−1)+n

如果我们应用大师定理,那么:

Θ(n∗logn) < Θ(T(n)) < Θ(2n)

请记住,T(n) = T(n-1) + T(n/2) + n渐近)大于 T(n) = T(n-1) + n 仅适用于渐近正函数。在这种情况下,我们有 T = Ω(n^2).

请注意 T(n) = -2(n + 2) 是函数方程的解,但我们不感兴趣,因为它不是 渐近正 解,因此符号O 没有有意义的应用。

您也可以轻松检查 T(n) = O(2^n)。 (参考yyFred解决方案,如有需要)

如果您尝试将 O 的定义用于 n^a(lgn)^b 类型的函数,其中 a(>=2)b 为正常数,您会发现这也不是一个可能的解决方案替换法。

事实上,唯一允许用代入法证明的函数是指数函数,但我们知道这种递归的增长速度不如 T(n) = 2T(n-1) + n,所以如果 T(n) = O(a^n),我们可以有 a < 2.

假设 T(m) <= c(a^m),对于某些常量 c,实数和正数。我们的假设是这种关系对所有 m < n 都有效。尝试针对 n 证明这一点,我们得到:

T(n) <= (1/a+1/a^(n/2))c(a^n) + n

我们可以通过用低阶项改变假设来轻松摆脱 n。这里重要的是:

1/a+1/a^(n/2) <= 1

a^(n/2+1)-a^(n/2)-a >= 0

更改变量:

a^(N+1)-a^N-a >= 0

我们希望找到尽可能紧的键,因此我们正在寻找尽可能低的 a。我们在上面发现的不等式接受非常接近 1 的 a 的解,但是否允许 a 任意接近 1?答案是否定的,令 a 的形式为 a = (1+1/N)。在不等式处代入 a 并应用极限 N -> INF:

e-e-1 >= 0

这是荒谬的。因此,上面的不等式有一些固定数 N* 作为最大解,可以通过计算找到。一个快速的 Python 程序让我找到了 a < 1+1e-45(有一点外推),所以我们至少可以确定:

T(n) = ο((1+1e-45)^n)