减少算法的时间复杂度

Question

这是从codility中获取的任务,需要O(n)复杂性.虽然我已经解决了它给出正确结果的任务,但时间复杂度为O(n*n).在解释如何将复杂性降低到O(n)时,将不胜感激.

任务描述:

给出了由N个整数组成的非空零索引数组A. 数组A表示磁带上的数字.

任何整数P,使得0 <P <N,将该磁带分成两个非空部分:A [0],A [1],...,A [P-1]和A [P],A [ P + 1],...,A [N - 1].

两部分之间的差异是:|(A [0] + A [1] + ... + A [P - 1]) - (A [P] + A [P + 1] + .. .+ A [N - 1])|

换句话说,它是第一部分的总和与第二部分的总和之间的绝对差.

例如,考虑数组A,使得:

A [0] = 3 A [1] = 1 A [2] = 2 A [3] = 4 A [4] = 3

我们可以在四个地方拆分这个磁带:

    P = 1, difference = |3 ? 10| = 7
    P = 2, difference = |4 ? 9| = 5
    P = 3, difference = |6 ? 7| = 1
    P = 4, difference = |10 ? 3| = 7

写一个函数:

int solution(vector<int> &A);

在给定N个整数的非空零索引数组A的情况下,返回可以实现的最小差异.

例如,给定:

A [0] = 3 A [1] = 1 A [2] = 2 A [3] = 4 A [4] = 3

该函数应返回1,如上所述.

假使,假设:

    N is an integer within the range [2..100,000];
    each element of array A is an integer within the range [?1,000..1,000].

复杂:

    expected worst-case time complexity is O(N);
    expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

可以修改输入数组的元素.

My solution:  
int solution(vector<int>& A)
{
    // write your code in C++11
    int result = std::numeric_limits<int>::max();
    int part_1 = 0;
    int part_2 = 0;
    for (auto beg = A.cbegin(), end = A.cend(); beg != prev(end); ++beg)
    { 
        part_1 = accumulate(A.cbegin(),beg + 1,0);
        part_2 = accumulate(beg + 1,end,0);
        int current_result = abs(part_1 - part_2);
        if (current_result < result)
        {
            result = current_result;
        }

    }

    return result;
}

Answer 1

我们S[i] = sum of the first i elements.您可以使用单个for循环计算:

S[0] = A[0]
for (int i = 1; i < n; ++i)
  S[i] = S[i - 1] + A[i]

然后,对于每个索引0 < i < n,直到的总和i - 1是简单的S[i - 1].从i数组到结尾的总和是S[n - 1] - S[i - 1]:

S[n - 1] = A[0] + ... + A[n - 1]
S[i - 1] = A[0] + ... + A[i - 1]

0 < i < n

S[n - 1] - S[i - 1] =  A[0] + ... + A[i - 1] + A[i] + ... + A[n - 1] -
                      (A[0] + ... + A[i - 1])
                    = A[i] + ... + A[n - 1]

在计算之后S,运行另一个循环并检查两个和之间的差异,这些差异是按照O(1)我所描述的计算的:

for (int i = 1; i < n; ++i)
{
  sum_left = S[i - 1]
  sum_right = S[n - 1] - S[i - 1]

  // see if |sum_left - sum_right| is better than what you have so far
}

时间复杂度是O(n)因为您只运行两个for循环,其中您只O(1)在每次迭代时执行操作.内存复杂性是O(n)因为您必须存储S,这与您的输入大小相同.

声明S如int[n]要细评审通过我们允许做的假设.