假设我们下面有两个不同版本的归并排序。对于一般用途，合并函数将合并输入的列表并返回一个全新的列表。
def merge_sort(items):
if len(items) <= 1:
return items
middle_index = len(items) // 2
left_split = items[:middle_index]
right_split = items[middle_index:]
left_sorted = merge_sort(left_split)
right_sorted = merge_sort(right_split)
return merge(left_sorted, right_sorted)
def merge_sort(items):
if len(items) <= 1:
return items
middle_index = len(items) // 2
left_sorted = merge_sort(items[:middle_index])
right_sorted = merge_sort(items[middle_index:])
return merge(left_sorted, right_sorted)
我的问题是：这两个函数的空间复杂度会有所不同吗？ （注意：当我提到空间复杂度时，我指的是辅助空间复杂度）
我学会了如何从最基本的角度计算递归函数的空间复杂度。简而言之，我们正在寻找递归在执行期间将占用的最大空间。当我们一直递归到我们的基本情况时，这通常是实现的，这意味着调用堆栈包含最大数量的帧——每个帧包含特定数量的数据。这可以用以下等式总结：
$$S(n) = \sum_{i=0}^最大递归深度 k$$ （其中k表示单个函数在i（level）方面占用的空间量）
考虑到第一个函数，我们在第一次递归调用之前创建两个长度为 1/2n 的列表（以及用于其他计算的常量琐碎空间，我们将忽略这些计算的简洁性）。因此，第一个函数调用 initially 在第一次递归调用之前占用 n 总空间，其中 n 是原始输入。在下一个递归调用中，我们正在处理一个大小为 1/2n 的列表。同样，在随后的递归调用之前，我们创建了两个 1/4n 长度的列表（总共 1/2n 空间）。因此，由于归并排序的最大递归深度为 log2n，我们可以为基本情况下占用的总空间创建一个一般求和：
$$S(n) = \sum_{i=0}^((log_2 n) - 1)(0.5)^i + 0$$
注意：我们只对倒数第二层求和，因为最后一层（基本情况）不会创建新列表；因此，最终递归调用的空间复杂度只是常量空间，这在这个例子中是微不足道的。当然，如果我在数学上更严谨一点，那么每个级别（包括最终级别）除了其各自的列表创建所占用的空间外，还将占用一定数量的空间。然而，在大 O 符号的镜头中，这个常数空间项将变得微不足道。因此，为了简洁起见，我将忽略它并添加一个“0”项来表示基本案例级别。
考虑到第二个函数，我们在第一次递归调用之前创建一个长度为 1/2n 的列表（以及用于其他计算的常量琐碎空间，我们将忽略这些计算的简洁性）。因此，第一个递归调用之前的第一个函数 call initially 占用总空间的 1/2n，其中 n 是原始输入。在下一个递归调用中，我们正在处理一个大小为 1/2n 的列表。同样，在后续递归调用之前，我们创建了一个 1/4n 长度的列表（总共 1/4n 空间）。因此，由于归并排序的最大递归深度为 log2n，我们可以为基本情况下占用的总空间创建一个一般求和：
$$S(n) = \sum_{i=0}^((log_2 n) - 1) 1/2n(0.5)^i + 0$$
注意：我们只对倒数第二层求和，因为最后一层（基本情况）不会创建新列表；因此，最终递归调用的空间复杂度只是常量空间，这在这个例子中是微不足道的。当然，如果我在数学上更严谨一点，那么每个级别（包括最终级别）除了其各自的列表创建所占用的空间外，还将占用一定数量的空间。然而，在大 O 符号的镜头中，这个常数空间项最终将变得微不足道。因此，为了简洁起见，我将忽略它并添加一个“0”项来表示基本案例级别。
虽然我知道这两个求和都会简化为相同的大 O 符号 O(n)，但我很好奇我的理解是否正确。由于第二个函数等到第一次递归调用之后才创建第二个列表，因此当我们最终达到基本情况时，整个函数调用实际上占用的空间更少。相反，第一个函数在第一次递归调用之前创建了两个列表，这意味着我们在每个递归调用中利用双倍的空间向下到基本情况。因此，在任何给定时间，第一个函数将占用双倍的空间。然而，在这种情况下，空间差异似乎微不足道。
在这个正确的解释？