How to calculate the worst-case runtime of this search-algorithm
https://softwareengineering.stackexchange.com/questions/219584
-
01-10-2020 - |
Вопрос
I've written a special indexOf
function for a list of unsorted unique values.
I can search for one or multiple (unsorted) values, passed as array/list, and the function will return me an array/list of indices (possibly empty).
Based on the following circumstances:
- I know that the values i'm searching for are in the list
- I don't care about the order in which the indices are returned
- Uniqueness
I'm doing the following:
- Walk through the list (of size n)
- Compare the values with all values in the search-list
- If there's a match break, add to results, break out of the loop and remove the found value from the search-list (so it's smaller on the next item)
- If there are no more values left to search for, break out of the list-traversal.
I'd like to know how to analyse this algorithm, and specifically what the worst-case runtime is. (I guess if I'm searching for all values contained in the list.)
Source in JavaScript:
function multipleIndexOf(search, arr) {
var searchArr = search.slice(0);
var result = [];
/* loop through array */
for (var i = 0, l = arr.length; i < l; i++) {
/* loop through search values */
for (var i2 = 0, l2 = searchArr.length; i2 < l2; i2++) {
/* if a search value matches... */
if (arr[i] == searchArr[i2]) {
/* add to result */
result.push(i);
/* remove from array */
searchArr.splice(i2, 1);
/* continue search with next */
break;
}
}
if (searchArr.length == 0) {
break;
}
}
return result;
}
Решение
You're going through each item in one collection for each item in another, that's O(N * M) where n and m are the sizes of each collection. The short circuiting doesn't affect the big O representation, as it is measuring the worst case, in which you never exit early. And even in the average case, the short circuiting cuts the time in half. O(N * M / 2) is equivalent to O(N * M).