Is looping an array to compare to itself considered O(n^2)? [duplicate]
https://softwareengineering.stackexchange.com/questions/414588
-
14-03-2021 - |
質問
Often when I'm doing an operation comparing an array to itself, I write code along these lines:
function operation (array) {
for (let i = 0; i < array.length; i++) {
for (let j = i + 1; j < array.length; j++) {
// do something with array, i, and j
}
}
}
While the runtime of this code (starting j
at i + 1
) is clearly faster than a normal double-nested loop, I'm struggling to figure out if that's just a matter of a smaller coefficient or if it should be represented by a different big O.
Is there a better big O for the above function than n squared?
解決
It's still O(n^2), with a constant coefficient of 1/2.
The number of times the inner loop is executed is (i-1) + (i-2) + (i-3) ... + 3 + 2 + 1
with the total number of terms being i
. Note that the first and last term add up to i
, as do the second and second-to-last, etc. So there are i/2
pairs, each of which adds up to i
- which makes a total of i/2 * i = 1/2 * i^2
This is actually the idea famously used by an elementary school aged Carl Friedrich Gauss circa 1785 to outwit his teacher on a make-work assignment.
他のヒント
Of course, if you know that the data is sorted, you would most certainly use a more intelligent algorithm, such as "binary search."
If you "brute-force loop through the array, without any consideration of its known properties," then of course you richly deserve your fate.