这段寻找两个有序数组中位数的代码空间复杂度是多少？

嘿，你的判断完全正确！这段递归实现的空间复杂度确实是O(log(m+n))，我来给你拆解背后的逻辑：

首先，咱们先锚定这个经典分治算法的核心思路：每次调用findKthSmallest时，都会通过对比两个数组的中间元素，排除掉约k/2个不可能是第k小的元素，把问题规模直接缩小一半左右。这个过程会一直递归下去，直到k=1或者其中一个数组的搜索范围为空。

那空间复杂度的核心来源是什么？是递归调用栈的深度：

• 每一层递归只会占用常数级别的空间（用来存储数组长度、起始索引、当前目标k值这些局部变量），所以总的空间开销完全由递归的层数决定。
• 因为每次问题规模都会减半，递归的深度自然是对数级别的——也就是log2(m+n)。毕竟从总长度m+n缩小到1，需要约log(m+n)次减半操作。

举个直观的例子：如果两个数组总长度是16，递归深度就是4（16→8→4→2→1，共4层调用栈）；如果总长度是1000，深度大概是10，完全符合对数级的增长趋势。

要是换成迭代实现这个分治逻辑，空间复杂度就能降到O(1)（不需要维护递归调用栈），但你的这段递归代码确实是O(log(m+n))的空间复杂度，和你的判断一致。

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