algorithm - 以下递归的时间复杂度？

Question

找出递归的时间复杂度(Big Oh Bound)T(n) = T(⌊n⌋) + T(⌈n⌉) + 1。

这个时间复杂度是如何变成O(n)的？？

Answer 1

你可能会提到 T(n)=T(⌊n/2⌋)+ T(⌈n/2⌉) + 1。

让我们计算 T(n) 的前几个值。

T(1) = 1
T(2) = 3
T(3) = 5
T(4) = 7

我们可以猜测 T(n) = 2 * n - 1。

让我们用 mathematical induction 来证明

基础

T(1) = 1
T(2) = 3
T(3) = 5
T(4) = 7

归纳步骤

T(2*n) = T(⌊2*n/2⌋)+ T(⌈2*n/2⌉) + 1  
   = T(⌊n⌋)+ T(⌈n⌉) + 1 
   = (2*n - 1) + (2*n - 1) + 1 
   = 4*n - 1
   = 2 * (2*n) - 1

T(2*n+1) = T(⌊(2*n+1)/2⌋)+ T(⌈(2*n+1)/2⌉) + 1
   = T(n)+ T(n+1) + 1
   = (2*n - 1) + (2*(n+1) - 1) + 1 = 
   = 4*n + 1 =
   = (2*n+1)*2 - 1

既然基础和归纳步骤都被证明了，现在通过数学归纳法证明T(n)对所有自然数2*n - 1都成立。

T(n) = 2*n - 1 = O(n)