logo标签列表

解决递归关系： T(n)=T(n-1)+T(n/2)+n

algorithmmathbig-orecurrence
5

解决方案：T(n)=T(n-1)+T(n/2)+n。

我尝试使用递归树来解决这个问题。有两个分支T(n-1)和T(n/2)。 T(n-1)会深入更高的深度。所以我们得到了O(2^n)。这个想法正确吗？

4
@hevi 这是一个算法问题，而不是数学问题。因此在这里发布问题是可以的，尽管http://cs.stackexchange.com/可能会更好一些。 - Erick G. Hagstrom
7个回答
5
这是一篇关于计算机科学的非常奇怪的递归。从一个角度看， T(n) = T(n-1) + T(n/2) + n 大于 T(n) = T(n-1) + n，它是O(n^2)。但从另一个角度看，这个 函数方程 有一个精确的解： 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的值。
O(n)包含在O(2^n)中，所以他的想法可能仍然是正确的。但是你只能在找到实际解决方案之前假设T(n)=o(n^2)，才能说T(n)-T(n-1)=o(n)。 - Teepeemm
1
T(n) = -2n 的计算意义是什么？通常当我说 T(n) = n 时，这意味着具有这种递归关系的算法在停止之前将执行确切的 n 个基本步骤（给定输入 n）。那么 T(n) = -2n 是什么意思？ - Ritwik
我非常确定 T(n) = T(n-1)+θ(n) = O(n^2) 和 T(n) = T(n/k)+θ(n) = O(n)。所以我不相信 T(n) = T(n/2)+T(n-1)+θ(n) 将是 O(n^2)，而且必须比这更高阶。这个链接 证明了它是 O(n^(log n))。所以我认为答案是错误的。你能检查一下吗？ - MsA
@anir。这个递归非常奇怪。从一个角度来看，我清楚地看到为什么解决方案O(n^2)是合理的，但在同一时间点，这个函数方程有一个精确的解：T(n)=-2n-4。将会更新答案。 - Salvador Dali
1

我认为你是正确的。递归关系总是会分成两个部分，即T（n-1）和T（n/2）。看看这两个部分，显然n-1的值减少速度比n/2慢，或者换句话说，你将从树的n-1部分拥有更多的分支。尽管如此，在考虑大O符号时，只需要考虑“最坏情况”，在本例中即是两侧的树都减少n-1(因为它减速更慢，需要更多的分支)。总之，你需要将关系分成两个共n次，因此你说O（2 ^ n）是正确的。

1
你的推理是正确的，但你透露了太多信息。（例如，说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

which reduces to

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) 增长速度的好方法（我已经盯着它看了几个月）。我唯一可以结束的事情是引用另一个答案：“对于计算机科学课程来说，这是一个非常奇怪的递归”。

0

我认为我们可以这样看待它：

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)

0
首先，我对接受的答案中有几个地方不同意：
1. 假设 T(n)=-2n+a 得到的确切解应该是 T(n) = -2(n+1) 而不是 T(n) = -2(n+2)。
2.
引用：

T(n) = T(n-1) + T(n/2) + n 大于 T(n) = T(n-1) + n

以这种方式进行比较是没有意义的，因为这两个递归中的 T(n) 不是相同的。
如果我们使用树的方法，假设第i层（从0开始计数）的总额外工作量（行总和）为S(i)。通过观察前几层，可以知道S(i)=3/2*S(i-1)+2^(i-1)，且S(0)=n。通过代入法解决这个递归式，我们得到S(i)=(3/2)^i*n-2^(i+1)+3*(3/2)^(i-1)。假设基本情况是T(1)=1，那么T(n)是i从0到n-1的S(i)的总和。
0

记住 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 的解决方案）

如果您尝试使用形式为 n^a(lgn)^b 的函数的 O 定义，其中 a(>=2) 和 b 是正常数，您会发现这也不是一个可能的解，通过代换方法进行检验。

实际上，只有指数函数允许使用代换法进行证明，但我们知道这个递归不会像“T(n) = 2T(n-1) + n”那样快速增长，因此如果“T(n) = O(a^n)”，我们可以有“a < 2”。
假设对于某个常数c、实数和正数a，有“T(m) <= c(a^m)”，我们的假设是这个关系对于所有“m < 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 = (1+1/N)。将a代入不等式并应用极限N -> INF：

e-e-1 >= 0

这是荒谬的。因此，上述不等式有一个固定的最大解N*，可以通过计算找到。一个快速的Python程序让我发现a < 1+1e-45（稍微外推一下），所以我们至少可以确定：

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

T(n) = T(n-1) + T(n/2) + n 和 T(n)=T(n)+T(n/2)+n 是等价的，因为我们在求极大值的情况下。只有当 T(n/2) + n = 0 时，T(n)=T(n)+T(n/2)+n 才成立。这意味着 T(n) = T(n) + 0 ~= O(n)。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接