求下述递归函数的时间复杂度，验证自推分析是否正确

函数代码 #

recursiveFunction(List<Input> list, int leftIndex, int rightIndex){

      // 递归终止条件满足时，生成对应输出。否则执行以下处理

      midIndex = (leftIndex + rightIndex) / 2

      List<Input> leftHalf = Generate_Left_Half_Of_Input_list
      List<Input> rightHalf = Generate_Right_Half_Of_Input_list

      if(!someFunction(leftHalf)){
          recursiveFunction(list, leftIndex, midIndex);
      } else if(!someFunction(rightHalf)){
          recursiveFunction(list, midIndex, rightIndex);
      } else {
          // 从输入列表生成4个子列表，每个子列表的规模都是当前递归调用输入规模的1/2
          // 对这4个子列表调用someFunction，如果其中某个列表调用返回false，则对该列表调用recursiveFunction
          // 注意：无论走哪个if/else分支，下一层递归调用的输入规模都是当前层的1/2
      }
}

辅助函数说明 #

someFunction的耗时与输入规模成正比：输入规模为n时耗时k，输入规模为n/2时耗时k/2。

我的分析与疑问 #

我认为该函数的时间复杂度为O(n log n)，理由是每一步输入规模都会减半，且每步最多有一次递归调用。someFunction的耗时与n成正比，且随n同步减半，所以认为其对整体复杂度的贡献为常数级（比如2n log n），会在大O表示法中被忽略。

我已完成的工作：

• 查阅了主定理（Master Theorem），认为不适用，因为递归外的耗时f(n)不是多项式。
• 用递归树（Recursive Tree）方法得到表达式5T(n/2) + n/2，这与归并排序的表达式类似，而归并排序的复杂度为O(n log n)。

请问正确答案是什么？

分析结论 #

你的判断是正确的，该函数的时间复杂度确实是O(n log n)，具体推导如下：

1. 递归深度
   无论走哪条分支，每次递归的输入规模都是上一层的1/2，因此从初始规模n到终止条件（规模为1）的递归深度为log₂n。

2. 每一层的时间开销

   • 前两个分支：当前层会执行2次someFunction，每次处理规模为n/2的子列表，总耗时为2*(n/2) = n，属于O(n)级。
   • 第三个分支：当前层先执行2次规模n/2的someFunction，再执行4次规模n/2的someFunction，总耗时为2*(n/2) + 4*(n/2) = 3n，同样属于O(n)级。
     大O表示法只关注最高量级，因此每一层的时间开销统一为O(n)。

3. 总时间复杂度计算
   递归树共有log₂n层，每层时间开销为O(n)，总时间复杂度为O(n * log n)。

另外需要纠正你递归树表达式的偏差：每次递归只会发起1次子调用，而非5次。正确的递归式应为T(n) = T(n/2) + O(n)（无论哪种分支情况），因为当前层非递归耗时都是O(n)，且仅触发一次规模为n/2的递归。

这类递归式用递归树求和或代入法均可推导得到O(n log n)的结果，逻辑和归并排序一致。主定理虽不适用，但递归树和代入法足以解决该问题。

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