求解递推关系: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-1
和 n
差不多。所以可以改写成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)+n
与 T(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=-2
和b=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)
求解: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-1
和 n
差不多。所以可以改写成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)+n
与 T(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=-2
和b=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)