algorithm - T(n) = 2T(n/2) +O(1) 的时间复杂度是多少

Question

我想知道我的递归方法的时间复杂度是多少: 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) 

Answer 1

我认为您对递归关系的理解是错误的。你可以这样想:

如果 T(n) 表示函数 T() 在输入 = n 时的值，则该关系表示输出是当前输入的一半时的值的两倍。因此，对于输入 = n-1 输出，即 T(n-1) 将是该输入一半值的两倍多，即 T(n-1) = 2*T((n-1)/2) + 1

上述递归关系应该按照 Yves Daoust 的回答来解决。更多递归关系的例子可以引用this