Space 下面函数的复杂度

Question

    public static int FindEquilibrumPoint(int[] arr)
    {
        int size = arr.Length;

        var prefixSum = new int[arr.Length];
        var suffixSum = new int[arr.Length];

        prefixSum[0] = arr[0];
        suffixSum[size - 1] = arr[size - 1];

        // Prefix Sum
        for (int i = 1; i < size; i++)
        {
            prefixSum[i] = prefixSum[i - 1] + arr[i];
        }

        // Suffix Sum
        for (int j = size-2; j > 0; j--)
        {
            suffixSum[j] = suffixSum[j + 1] + arr[j];
        }

        for (int i = 0; i < size; i++)
        {
            if (prefixSum[i] == suffixSum[i])
                return arr[i];
        }
        return -1;
    }

我猜时间复杂度是O(n) 但是我对如何计算 space 复杂度感到困惑。 Space 复杂度是多少？

Answer 1

您分配了两个长度为 n 的数组，其中 n 是算法输入的大小。您使用的 space 的其余部分不依赖于您的输入（常量 space）。因此，我们可以将您的 space 用法（如果不计算输入数组本身）表示为：

2n+c

其中 c 是某个常数。现在，类似于时间复杂度，我们可以用 big-O 表示法表示算法的 space 复杂度：

O(2n + c) = O(n)

你似乎已经知道 big-O 表示法在时间复杂度的上下文中是如何工作的，所以我怀疑这一步是否需要在这里解释（关键是它是相同的表示法，所以相同的规则申请）。因此，您的 space 复杂度是 O(n)，就像您的时间复杂度一样。

Space 下面函数的复杂度

Space Complexity of the Below Function

c#

big-o

space-complexity