基于主定理分析递归函数的数字与1的打印次数问题

给定递归函数：

Function f(n):
 if(n>=1)
    for i=1 to n:
       print(i)
 f(n/2)
 f(n/2)

假设 ( n=2^k )，( k≥1 )，以下分别分析两个问题：

a) 总共打印的数字个数 #

推导递归关系 #

设 ( T(n) ) 为输入为 ( n ) 时打印的总数字个数：

• 当 ( n≥1 ) 时，当前函数的循环会打印 ( n ) 个数字；
• 随后两次递归调用 ( f(n/2) )，每个调用的打印次数为 ( T(n/2) )；
• 边界条件：( T(1)=1 )（输入为1时仅打印1个数字）。

因此递归式为：
[ T(n) = 2T(n/2) + n ]

主定理求解 #

主定理形式为 ( T(n) = aT(n/b) + f(n) )，对应这里：

• ( a=2 )（递归子问题数量），( b=2 )（子问题规模缩小比例）；
• ( f(n)=n )，计算 ( \log_b a = \log_2 2 = 1 )；
• ( f(n) = \Theta(n^{\log_b a}) )，符合主定理第二种情况，因此：
  [ T(n) = \Theta(n \log n) ]

展开验证（( n=2^k )）：
[
\begin{align*}
T(2^k) &= 2T(2^{k-1}) + 2^k \
&= 2^k T(1) + k \cdot 2^k \
&= 2^k + k \cdot 2^k \
&= n(1 + \log_2 n)
\end{align*}
]
显然属于 ( \Theta(n \log n) )。

b) 数字1被打印的次数 #

推导递归关系 #

设 ( S(n) ) 为输入为 ( n ) 时数字1被打印的次数：

• 当 ( n≥1 ) 时，当前函数的循环会打印1一次；
• 随后两次递归调用 ( f(n/2) )，每个调用中1被打印 ( S(n/2) ) 次；
• 边界条件：( S(1)=1 )（输入为1时仅打印1一次）。

因此递归式为：
[ S(n) = 2S(n/2) + 1 ]

主定理求解 #

对应主定理参数：

• ( a=2 )，( b=2 )，( \log_b a = 1 )；
• ( f(n)=1 = \Theta(n^0) )，且 ( 0 < 1 )，满足 ( f(n) = O(n^{\log_b a - \varepsilon}) )（取 ( \varepsilon=0.5 ) 即可），符合主定理第一种情况，因此：
  [ S(n) = \Theta(n) ]

展开验证（( n=2^k )）：
[
\begin{align*}
S(2^k) &= 2S(2^{k-1}) + 1 \
&= 2^k S(1) + (2^{k-1} + 2^{k-2} + ... + 1) \
&= 2^k + (2^k - 1) \
&= 2n - 1
\end{align*}
]
显然属于 ( \Theta(n) )。

内容的提问来源于stack exchange，提问作者Nikolaos Bekertzis