我想知道我的递归方法的时间复杂度：
t（n）=2t（n/2）+o（1）
我看到一个结果，它是o（n），但我不知道为什么，我这样解决了它：
T(n) = 2T(n/2) + 1
T(n-1) = 4T(n-1/4) + 3
T(n-2) = 8T(n-2/8) + 7
...... ………….. ..
T(n) = 2^n+1 T (n/2^n+1) + (2^n+1 - 1)
最佳答案
我认为你对递归关系的理解是错误的你可以这样想：
如果T（n）表示函数T（）在input=n时的值，则关系表示输出是当前输入一半时的值的两倍所以对于输入=n-1输出，即t（n-1）将是这个输入的一半的两倍以上，即t（n-1）=2*t（（n-1）/2）+1
上面这种递归关系应该按照yves daoust的回答来解决。有关递归关系的更多示例，可以参考this
关于algorithm - T(n)的时间复杂度= 2T(n/2)+ O(1)是多少，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53226482/