Sum of all continuous optimization of the sub-machine
I solve a problem when I have a larger array and for a given two numbers I need to find the sum of all adjacent subarrays in between.
All I could think of was O (n 2 ) code
for(i = min; i<= max; ++i)
{
sum = 0;
for(j = i; j <= max; ++j)
{
sum+=a[j];
printf("%lld\n", sum);
}
}
Can anyone help me optimize this code?
If max-min+1
- n
, there will be n(n-1)/2
amounts to be printed. O (n 2 ) values . The fastest algorithm for getting O (n 2 ) values would have a time complexity of O (n 2 ), so your solution is already optimal.
Using dynamic programming you can get the answer O(n)
. The basic idea is to calculate the prefix sums accumulated for all elements.
Let be the A(i)
summation of elements from 0
to i
. It can be easily computed in O (n) like this:
// let your array by Src[Max]
int A[MAX];
A[0] = Src[0];
for(int i=1; i<MAX; i++) A[i] +=A[i-1] + (i+1)*Src[i];
Then for any elements i and j you can calculate sum(i,j) = A[j] - A[i]
(adjust the boundaries depending on the input requirements).
There is no faster solution.
Since your output size is O (n 2 ), the algorithm couldn't be faster.
For an insanely large block of computation, or things like real-time data analysis, since the contents of the arrays do not change, you can perform computations in parallel threads.
For general cases, just loop them and let the compiler expand and use the vectorized instructions.