用迭代、替换、主定理解决递归问题？

Question

我熟悉用迭代解决递归问题：

t(1) = c1
t(2) = t(1) + c2 = c1 + c2
t(3) = t(2) + c2 = c1 + 2c2
...
t(n) = c1 + (n-1)c2 = O(n)

但是，如果我在没有基本案例的情况下再次出现怎么办？题中提到的三种方法如何解决？

t(n) = 2t(n/2) + 1

对于Master Theorem我知道第一步，找到a、b和f(n):

a = 2
b = 2
f(n) = 1

但不知道从这里去哪里。我处于停滞状态，因为我不确定如何处理这个问题。

Answer 1

我知道有两种方法可以解决这个问题：

(1) T(n) = 2T(n/2) + 1
(2) T(n/2) = 2T(n/4) + 1
now replace T(n/2) from (2) into (1)

T(n) = 2[2T(n/4) + 1] + 1
     = 2^2T(n/4) + 2 + 1

T(n/4) = 2T(n/8) + 1
T(n) = 2^2[2T(n/8) + 1] + 2 + 1
     = 2^3T(n/8) + 4 + 2 + 1

你会一直这样做，直到你可以概括。最终你会发现：

T(n) = 2^kT(n/2^k) + sum(2^(k-1))

你想要 T(1) 所以设置 n/2^k = 1 并求解 k。当你这样做时你会发现，k = lgn

将 lgn 替换为 k 您将得到

T(n) = 2^lgnT(n/2^lgn) + (1 - 2^lgn) / (1 - 2)
2^lgn = n so,

T(n) = nT(1) + n - 1
T(n) = n + n - 1 where n is the dominant term.

Master Theorem 真的很快

Consider, T(n) = aT(n/b) + n^c for n>1

一共有三种情况（注意b是log底）

(1)  if logb a < c, T(n)=Θ(n^c),

(2)  if logb a = c, T (n) = Θ(n^c log n),

(3)  if logb a > c, T(n) = Θ(n^(logb a)).

在这种情况下，a = 2，b = 2，c = 0 (n^0 = 1)

快速检查显示案例 3。

n^(log2 2)

note log2 2 is 1

So by master theorem this is Θ(n)

Answer 2

除了Master Theorem，Recursion Tree Method和Iterative Method还有so 称为 "Substitution Method"。

你经常会发现人们在谈论替换方法，实际上它们指的是迭代方法（尤其是在 Youtube 上）。我想这源于这样一个事实，即在迭代方法中你也在替换一些东西，即第 n+1-th 递归调用到 n-th one...

关于算法的标准参考书 (CLRS) 定义如下：

Substitution Method

Guess the form of the solution.

Use mathematical induction to find the constants and show that the solution works.

例如，让我们以您的递归方程为例：T(n) = 2T(ⁿ/₂)+1

我们猜测解是T(n) ∈ O(n²)，所以我们要证明 T(n) ≤ cn² 对于某个常量 c.
此外，让我们假设对于 n=1，您正在做一些持续的工作 c。

给定：

T(1) ≤ c
T(n) = 2T(ⁿ/₂)+1

求证：

∃c > 0, ∃n₀ ∈ ℕ, ∀n ≥ n₀, such that T(n) ≤ cn² is true.

基本情况：

n=1:  T(1) ≤ c    
n=2:  T(2) ≤ T(1) + T(1) + 1 ≤ 4c
             (≤c)   (≤c)      (cn²)

归纳步骤：

作为归纳假设，我们假设所有小于 n 的正数都为 T(n) ≤ cn² 特别是 (ⁿ/₂)。

因此T(ⁿ/₂) ≤ c(ⁿ/₂)²，因此

T(n) ≤ 2c(ⁿ/₂)² + 1     ⟵ Here we're substituting c(ⁿ/₂)² for T(ⁿ/₂)
     = (¹/₂)cn² + 1
     ≤ cn²  (for c ≥ 2, and all n ∈ ℕ)

所以我们已经证明，存在一个常数 c，因此 T(n) ≤ cn² 对所有 n ∈ ℕ 都成立。这意味着 T(n) ∈ O(n²)。 ∎

（对于 Ω，因此对于 Θ，证明是相似的）。

用迭代、替换、主定理解决递归问题？

Solving recurrences with iteration, substitution, Master Theorem?

algorithm

math

recurrence

asymptotic-complexity

Substitution Method