O(lgn)时间复杂度的2ⁿ计算算法正确性验证及递推关系问询

一、算法正确性分析 #

你给出的算法不正确，举个反例就能验证：
当n=4时，按照算法逻辑：
func(4) = 2 * func(2)
func(2) = 2 * func(1)
func(1) = 2 * func(0) = 21=2
所以func(2)=22=4，func(4)=2*4=8，但实际2⁴=16，结果明显错误。

错误原因是偶数分支的逻辑错误：当n为偶数时，2ⁿ=2^(2k)=(2k)²，而不是2*2^k，正确的偶数分支应该返回func(n/2)*func(n/2)（或者直接做平方操作），这样才能得到正确的2ⁿ结果。

二、分支递归的递推关系推导方法 #

对于带分支判断的递归算法，递推关系需要分情况对应不同分支来写，核心是看每个分支里实际递归调用了几个子问题，以及每个子问题的规模：

1. 定义T(n)为计算func(n)所需的时间复杂度
2. 基准情况：当n=0时，仅执行判断和返回操作，时间为常数，即T(0)=O(1)
3. 偶数分支（n为偶数且n>0）：算法只递归调用1次func(n/2)，加上判断、乘法等常数操作，递推式为：T(n) = T(n/2) + O(1)
4. 奇数分支（n为奇数且n>0）：算法只递归调用1次func(n-1)，加上判断、乘法等常数操作，递推式为：T(n) = T(n-1) + O(1)

三、你给出的递推式是否正确？ #

完全不正确。你的递推式T(n) = 2T(n-2) + 2T(n-1) + O(1)暗示每次计算func(n)会同时调用2次func(n-2)和2次func(n-1)，但实际算法每个分支只会触发一次递归调用，根本不存在多个子问题的并行调用，所以这个递推式完全不符合算法的实际执行逻辑。

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