降低算法的时间复杂度 [英] Reducing time complexity of an algorithm
问题描述
这是一个取自codility的任务，它需要O(n)的复杂度.虽然我已经解决了它给出正确结果的任务，但时间复杂度是 O(n*n).感谢您在解释如何将复杂性降低到 O(n) 方面的任何帮助.
This is a task taken from codility, which requires O(n) complexity. Although I've solved the task that it gives correct results, the time complexity is O(n*n). Would appreciate any help in explaining how to reduce that complexity to O(n).
任务描述:
给出一个由 N 个整数组成的非空零索引数组 A.数组 A 代表磁带上的数字.
A non-empty zero-indexed array A consisting of N integers is given. Array A represents numbers on a tape.
任何整数 P，使得 0
Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].
两部分的区别在于:|(A[0] + A[1] +... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|
The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|
换句话说，就是总和之间的绝对差第一部分和第二部分的总和.
In other words, it is the absolute difference between the sum of the first part and the sum of the second part.
例如，考虑数组 A 使得:
For example, consider array A such that:
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3
我们可以把这盘磁带分成四个地方:
We can split this tape in four places:
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，返回可以实现的最小差异.
that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved.
例如，给定:
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3
函数应该返回 1，如上所述.
the function should return 1, as explained above.
假设:
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).
可以修改输入数组的元素.
Elements of input arrays can be modified.
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;
}
推荐答案
让 S[i] = 前 i 个元素的总和.您可以使用单个 for 循环来计算:
Let S[i] = sum of the first i elements. You can compute this with a single for loop:
S[0] = A[0]
for (int i = 1; i < n; ++i)
S[i] = S[i - 1] + A[i]
然后，对于每个索引 0 <我＜n，直到 i - 1 的总和就是 S[i - 1].i 到数组末尾的和为 S[n - 1] - S[i - 1]:
Then, for each index 0 < i < n, the sum up until i - 1 is simply S[i - 1]. The sum from i to the end of the array is 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)中计算:
After computing S, run another loop and check the differences between the two sums, which are computed in O(1) like I described:
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，它的大小与你的输入相同.
The time complexity is O(n) because you only run two for loops in which you only do O(1) operations at each iteration. The memory complexity is O(n) because you have to store S, which is the same size as your input.
根据我们允许做出的假设，将 S 声明为 int[n] 应该没问题.
Declaring S as int[n] should be fine judging by the assumptions we're allowed to make.
这篇关于降低算法的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
