下面算法的 space 复杂度如何变成 O(log n)

Question

int[] findMinMax(int A[], int start, int end)
{
int max;
int min;
if ( start == end )
{
    max = A[start]
    min = A[start]
}
else if ( start + 1 == end )
{
    if ( A[start] < A[end] )
    {
        max = A[end]
        min = A[start]
    }
    else
    {
        max = A[start]
        min = A[end]
    }
}
else
{
    int mid = start + (end - start)/2
    int left[] = findMinMax(A, start, mid)
    int right[] = findMinMax(A, mid+1, end)
    if ( left[0] > right[0] )
        max = left[0]
    else
        max = right[0]
    if ( left[1] < right[1] )
        min = left[1]
    else
        min = right[1]
}
// By convention, we assume ans[0] as max and ans[1] as min
int ans[2] = {max, min}
 return ans
 }

使用递归主定理分析时间复杂度为O(n)。在查看伪代码时，很明显使用了分而治之的算法范式。我在 space 复杂性部分遇到困难。任何帮助将不胜感激？

Answer 1

你的数组 left 和 right 由对你的函数的递归调用填充。由于这些调用的输入在每次调用时不断减半，因此在到达根本不需要填充它们的基本情况之前，您只需要记录 n 次调用。因此，使用的辅助 space 的界限是 O(log n).

下面算法的 space 复杂度如何变成 O(log n)

How is the space complexity of below algorithm come out to be O(log n)

space-complexity