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) 但我對如何計算空間復雜度感到困惑。這是什么功能空間復雜度？
uj5u.com熱心網友回復：
您分配兩個長度為n的陣列，其中n是演算法輸入的大小。您使用的其余空間不取決于您的輸入（恒定空間）。因此，我們可以將您的空間使用情況（如果不計算輸入陣列本身）表示為：
2n c
其中c是某個常數。現在，與時間復雜度類似，我們可以用大 O 表示法表示演算法的空間復雜度：
O(2n c) = O(n)
您似乎已經知道大 O 符號在時間復雜度的背景關系中是如何作業的，所以我懷疑這一步需要在這里解釋（關鍵是它是相同的符號，所以適用相同的規則）。因此，您的空間復雜度是O(n)，就像您的時間復雜度一樣。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/448781.html