主方法 - 与两个 T 的递归关系
Master Method - Recurrence relation with two Ts
我正在上数据结构和算法课程（这很艰难）。我们了解了解决基本递归关系的主要方法，当它们的形式为 aT(n/b)+f(n) 时。现在我们已经了解了线性时间选择算法，它有一个不是这种形式的关系，我被要求找到它的更坏情况 运行 时间是渐近符号。
我发现递归关系为：
在我看来，Master Method 没有解释这一点 - 我很可能是错的。如果不是，那么你如何找到最坏情况 运行 时间？
主定理不适用，但直接证明此递归的紧界并不难。
你知道你不能比 O(n) 做得更好，因为那个词已经在循环中了。有人告诉你这是一个线性时间算法，根据一些经验，你会猜到子问题的总规模比 n 小了某个因子，所以你可以做 O(n).
剩下的就是证明了。
你可以通过归纳法很容易地证明这一点。设 C 是一个（大）常数，使得：
T(n) <= T(n/101 + 1) + T(151n/202 + 101) + C(n+1)/202,对于所有 n、（eq 1）和
T(n) <= C(n+1)，对于所有 n < 1000 (eq 2)
对于任何 n >= 1000，如果 (eq 2) 对所有较小的 n 成立，那么我们有
T(n) <= T(n/101 + 1) + T(151n/202 + 101) + C(n+1)/202 (当量 1)
T(n) <= C(n+202)/101 + C(151n+20604)/202 + C(n+1)/202 (subst eq 2)
T(n) <= C(2n+404)/202 + C(151n+20604)/202 + C(n+1)/202
T(n) <= C(156n+20604)/202
T(n) <= C(0.78n + 102) <= C(n - 0.22n + 102) <= C(n - 220 + 102) (因为 n>=1000)
T(n) <= C(n+1)
所以，如果我们像上面那样选择 C，那么 (eq 2) 对于 n < 1000 成立的事实意味着它对所有 n 成立，并且 T(n) 在 O(n)
中
我正在上数据结构和算法课程（这很艰难）。我们了解了解决基本递归关系的主要方法，当它们的形式为 aT(n/b)+f(n) 时。现在我们已经了解了线性时间选择算法，它有一个不是这种形式的关系，我被要求找到它的更坏情况 运行 时间是渐近符号。
我发现递归关系为：
在我看来，Master Method 没有解释这一点 - 我很可能是错的。如果不是，那么你如何找到最坏情况 运行 时间？
主定理不适用，但直接证明此递归的紧界并不难。
你知道你不能比 O(n) 做得更好，因为那个词已经在循环中了。有人告诉你这是一个线性时间算法，根据一些经验，你会猜到子问题的总规模比 n 小了某个因子，所以你可以做 O(n).
剩下的就是证明了。
你可以通过归纳法很容易地证明这一点。设 C 是一个（大）常数，使得：
T(n) <= T(n/101 + 1) + T(151n/202 + 101) + C(n+1)/202,对于所有 n、（eq 1）和
T(n) <= C(n+1)，对于所有 n < 1000 (eq 2)
对于任何 n >= 1000，如果 (eq 2) 对所有较小的 n 成立，那么我们有
T(n) <= T(n/101 + 1) + T(151n/202 + 101) + C(n+1)/202 (当量 1)
T(n) <= C(n+202)/101 + C(151n+20604)/202 + C(n+1)/202 (subst eq 2)
T(n) <= C(2n+404)/202 + C(151n+20604)/202 + C(n+1)/202
T(n) <= C(156n+20604)/202
T(n) <= C(0.78n + 102) <= C(n - 0.22n + 102) <= C(n - 220 + 102) (因为 n>=1000)
T(n) <= C(n+1)
所以，如果我们像上面那样选择 C，那么 (eq 2) 对于 n < 1000 成立的事实意味着它对所有 n 成立，并且 T(n) 在 O(n)
中