仅含一个n/2规模子调用的递归函数的大O时间复杂度如何计算

你给出的递归函数如下：

public static int div(int numItems)
{
    if (numItems == 0)
        return 0;
    else
        return numItems%2 + div(numItems/2);
}

你的初步判断是正确的，该函数的时间复杂度为O(log n)，具体推导逻辑和这类递归的通用判定规则如下：

单函数推导过程 #

定义T(n)为输入规模为n时，div函数的执行总开销：

• 终止条件：当n=0时，函数仅执行一次条件判断和返回操作，属于常数时间，即T(0) = C₁（C₁为固定常数）
• 非终止条件：每次函数调用时，除了递归调用子问题外，仅执行条件判断、取模、加法三个常数时间操作，开销为固定常数C₂，子问题的输入规模为n/2，因此递推式为：

  T(n) = T(n/2) + C₂

• 展开递推式计算总开销：

  T(n) = T(n/2) + C₂
  = T(n/4) + C₂ + C₂ = T(n/4) + 2*C₂
  = T(n/8) + 3*C₂
  ...
  = T(0) + k*C₂
  

  其中k是n连续除以2直到得到0的次数，显然k=log₂n，代入后总开销为T(n) = C₁ + C₂log₂n，忽略常数项和常数系数，最终大O表示为O(log n)*。

同类单分支减半递归的通用大O判定 #

所有仅包含1个输入规模为n/2的子递归调用的函数，都可以套用通用递推式*T(n) = T(n/2) + f(n)*计算时间复杂度，根据每次递归除子调用外的操作开销f(n)的等级，最终时间复杂度分别为：

• 若f(n)是常数级（即和输入规模n无关）：时间复杂度为O(log n)，本次的div函数就属于这类场景
• 若f(n)是O(n)级：递推展开后总开销为n + n/2 + n/4 + ... + 1 = 2n，时间复杂度为O(n)
• 若f(n)是O(nᵏ)级（k>1）：总开销的最高阶项为nᵏ，时间复杂度为O(nᵏ)

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