递归关系：T(n) = T(ceil(n/3)) + T(ceil(3n/5)) + 100*n
Recurrence relation: T(n) = T(ceil(n/3)) + T(ceil(3n/5)) + 100*n
我的递归关系为：
T(n) = T(ceil(n/3)) + T(ceil(3n/5)) + 100*n 和 T(1) = 1
我正在尝试使用递归树方法来解决它，但我不知道如何处理递归关系中的上限函数。
那么，如何找到 T(n) 的最紧渐近边界？
可以使用Akra-Bazzi theorem.。为此，您可以使用 ceil(x) = x + 1 - {x} 这样的事实，使得 {x} 是 x 的小数部分。
因此，您可以重写复杂性项，例如：
T(n) = T(n/3 + 1 - {n/3}) + T(3n/5 + 1 - {3n/5}) + 100n
因此，定理中的参数为：
a1 = a2 = 1,
b1=1/3, b2 = 3/5,
h1(n) = 1 - {n/3}, h2(n) = 1 - {3n/5},
g(n) = 100n
如您所见，0 < b1, b2 < 1、a1, a2 > 0、h1, h2 < 1 和 g(n) 是线性的。这意味着定理的所有要求都成立。
现在，是时候找到 p 使得：
(1/3)^p + (3/5)^p = 1 => p ~ 0.9
因此，T(n) = Theta(n^p (1 + int(100 u/u^{p+1}, 1, n))。
为了简化术语，我们需要计算积分：
int(100 u/u^{p+1}, 1, n) = 100 * int(1/u^p, 1, n) = 100 (n^{1-p}/(1-p) - 1)
所以复杂度的简化项是T(n) = Theta(n)。
@OmG 使用 Akra-Bazzi 定理的回答很好地展示了如何使用该数学工具。这是使用递归树查看为什么运行时间为 O(n) 的不同方法。
让我们从绘制递归树的顶两层开始：
+--------------------+
| n items, 100n work |
+--------------------+
/ \
+------------------------+ +-------------------------+
| n/3 items, 100n/3 work | | 3n/5 items, 300n/5 work |
+------------------------+ +-------------------------+
纯粹为了方便起见，我不考虑上限，因为它们不会对整体分析产生影响。
注意第二层所做的功等于
100n / 3 + 300n / 5 = 500n / 15 + 900n / 15 = 1400n / 15 = 100n * (14 / 15),
低于上一层的工作量。具体来说，这里的工作量几何级数减少了 14/15 倍。事实上，每次我们进行递归调用时，这两个子调用将共同完成其上一级工作的 14/15 部分。
这意味着所有递归调用完成的总工作是
(work in layer 0) + (work in layer 1) + (work in layer 2) + ...
≤ 100n + (14/15) · 100n; + (14/15)2 · 100n + (14/15)3 · 100n + ...
≤ 100n(1 + (14/15) + (14/15)2 + (14/15)3) + (14/15)4 + ...)
最后一个和是一个几何级数的和，结果是
1 / (1 - 14/15) = 1 / (1/15) = 15,
所以总共完成的功最多为 1500n。
直觉上，如果你看到像这样的递归树，其中每一层完成的工作从一个级别到下一个级别下降一个常数，那么完成的总工作将只是在顶部完成的工作的某个常量倍数等级。主定理及其推广 Akra-Bazzi 定理本质上是通过量化发生这种情况的条件并为它们提供精确的封闭形式解决方案来形式化这个想法。但是如果你在未来看到像这样的重复出现，工作从一个级别到另一个级别呈几何下降，你应该有一种“直觉”，即总共完成的工作最多将是顶级的一些倍数。
（您可以在中位数算法 T(n) = T(n / 5) + T(7n / 10) + n 的著名递归算法上尝试这个，其中有一个类似的衰减从树的一层到下一层。）
在做这个分析时，我忽略了所有的地板和天花板，这在数学上并非在所有情况下都安全。但在这里，它最终没问题，因为我们在每个级别上偏离的微小数量并不会在整个树上加起来那么多。为了证明这一点，您可以使用替换方法并尝试证明已完成工作的精确界限。
我的递归关系为：
T(n) = T(ceil(n/3)) + T(ceil(3n/5)) + 100*n 和 T(1) = 1
我正在尝试使用递归树方法来解决它，但我不知道如何处理递归关系中的上限函数。
那么，如何找到 T(n) 的最紧渐近边界？
可以使用Akra-Bazzi theorem.。为此，您可以使用 ceil(x) = x + 1 - {x} 这样的事实，使得 {x} 是 x 的小数部分。
因此，您可以重写复杂性项，例如：
T(n) = T(n/3 + 1 - {n/3}) + T(3n/5 + 1 - {3n/5}) + 100n
因此，定理中的参数为：
a1 = a2 = 1,
b1=1/3, b2 = 3/5,
h1(n) = 1 - {n/3}, h2(n) = 1 - {3n/5},
g(n) = 100n
如您所见，0 < b1, b2 < 1、a1, a2 > 0、h1, h2 < 1 和 g(n) 是线性的。这意味着定理的所有要求都成立。
现在，是时候找到 p 使得：
(1/3)^p + (3/5)^p = 1 => p ~ 0.9
因此，T(n) = Theta(n^p (1 + int(100 u/u^{p+1}, 1, n))。
为了简化术语，我们需要计算积分：
int(100 u/u^{p+1}, 1, n) = 100 * int(1/u^p, 1, n) = 100 (n^{1-p}/(1-p) - 1)
所以复杂度的简化项是T(n) = Theta(n)。
@OmG 使用 Akra-Bazzi 定理的回答很好地展示了如何使用该数学工具。这是使用递归树查看为什么运行时间为 O(n) 的不同方法。
让我们从绘制递归树的顶两层开始：
+--------------------+
| n items, 100n work |
+--------------------+
/ \
+------------------------+ +-------------------------+
| n/3 items, 100n/3 work | | 3n/5 items, 300n/5 work |
+------------------------+ +-------------------------+
纯粹为了方便起见，我不考虑上限，因为它们不会对整体分析产生影响。
注意第二层所做的功等于
100n / 3 + 300n / 5 = 500n / 15 + 900n / 15 = 1400n / 15 = 100n * (14 / 15),
低于上一层的工作量。具体来说，这里的工作量几何级数减少了 14/15 倍。事实上，每次我们进行递归调用时，这两个子调用将共同完成其上一级工作的 14/15 部分。
这意味着所有递归调用完成的总工作是
(work in layer 0) + (work in layer 1) + (work in layer 2) + ...
≤ 100n + (14/15) · 100n; + (14/15)2 · 100n + (14/15)3 · 100n + ...
≤ 100n(1 + (14/15) + (14/15)2 + (14/15)3) + (14/15)4 + ...)
最后一个和是一个几何级数的和，结果是
1 / (1 - 14/15) = 1 / (1/15) = 15,
所以总共完成的功最多为 1500n。
直觉上，如果你看到像这样的递归树，其中每一层完成的工作从一个级别到下一个级别下降一个常数，那么完成的总工作将只是在顶部完成的工作的某个常量倍数等级。主定理及其推广 Akra-Bazzi 定理本质上是通过量化发生这种情况的条件并为它们提供精确的封闭形式解决方案来形式化这个想法。但是如果你在未来看到像这样的重复出现，工作从一个级别到另一个级别呈几何下降，你应该有一种“直觉”，即总共完成的工作最多将是顶级的一些倍数。
（您可以在中位数算法 T(n) = T(n / 5) + T(7n / 10) + n 的著名递归算法上尝试这个，其中有一个类似的衰减从树的一层到下一层。）
在做这个分析时，我忽略了所有的地板和天花板，这在数学上并非在所有情况下都安全。但在这里，它最终没问题，因为我们在每个级别上偏离的微小数量并不会在整个树上加起来那么多。为了证明这一点，您可以使用替换方法并尝试证明已完成工作的精确界限。