Menu
I have the following algorithm which scan a large circular array (data). At certain point in the array, I need to take a look at the past values (0 = newest data point, n = oldest data point) and determine if there was a value 5% below the current value. I ended up writing a O(n^2) algorithm which works okay, but this doesn't scale.
const int numberOfDataPointsInPast = 1000;
int numberOfDataPoints = 0;
for (int i = numberOfDataPointsInPast; i >= 0; i--)
{
double targetPoint = data[i] * 0.95;
for (int j = i + numberOfDataPointsInPast; j > i; j--)
{
if (data[j] <= targetPoint)
{
numberOfDataPoints++;
break;
}
}
}
Any idea how I could transform this into a O(n) algo? Thanks!
894
O(N²) — Quadratic O(N²) represents the complexity of an algorithm, whose performance is proportional to the square of the size of the input elements. It is generally quite slow: If the input array has 1 element it will do 1 operation, if it has 10 elements it will do 100 operations, and so on.
An algorithm that is O(1) with a constant factor of 10000000 will be significantly slower than an O(n) algorithm with a constant factor of 1 for n < 10000000.
Save this question. Show activity on this post. If n<100 then O(n2) is more efficient, but if n≥100 then O(nlogn) is more efficient.
While iterating the array store the lowest value. This requires to create a min variable and perform a compare check in every step. Instead of comparing all previous values with the new one, compare it only with the lowest.
197
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
