如何找到除法递归函数的大O

Question

我正在学习 Big O，但遇到了一个问题。

问题 -

int sample_function (int x) {
 if (x<1){
   return x;}
  
 int y = x/2; 
 return sample_function (y) + sample_function (x-y);
}

如果我们对(n/2)进行2次递归调用，大O会是什么？我知道除法递归函数（n/2）的大O是O（log（n））但不确定这个问题。

Answer 1

T(n) = 2 * T(n / 2) + O(1) = 4 * T(n / 4) + 2 * O(1) = 8 * T(n / 8) + 4 * O(1) = ... = n * O(1) + (n / 2) * O(1)

所以，它是 O(n)。

Answer 2

将整数 x 除以 2 得到 0 大约需要 log2(x) 步。每一步都会使函数调用次数加倍。例如：

  8
  4               4
  2       2       2       2
  1   1   1   1   1   1   1   1
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

总共是 sum( 2^k ), k = 0 ...log2(x) = O(x)。

对于 0 并否定你 return 在第一次通话中，那就是 O(1)。

PS：可以说函数实际上是 O(1)。编译器可能会将其替换为：

int sample_function (int x) {
    if (x < 1) return x;
    else return 0;
}

Answer 3

递归关系的解法

T(n) = T(ceiling(n/2))+T(floor(n/2)) + O(1)

是

T(n) = O(n).

这可以通过对n的归纳来证明。归纳基础很简单。至于归纳步骤，令 c 为正常数，使得 T(ceiling(n/2)) 和 T(floor(n/2)) 的上限为 c * ceiling(n/2)和 c * floor(n/2)，分别。因此，T(n) 的上限为 c * (ceiling(n/2) + floor(n/2) = c * n.

如何找到除法递归函数的大O

How to find Big O of a dividing recursive function

big-o