Gdy zajmowałem się analizą wydajności algorytmów, natknąłem się na . Nie tylko daje ono wyobrażenie o tym, jak przebiegają rozmowy kwalifikacyjne w dużych korporacjach technologicznych, ale także pozwala zrozumieć, jak efektywnie rozwiązują się zadania algorytmiczne.
Ten artykuł stanowi swoiste uzupełnienie wideo. Zawiera komentarze do wszystkich przedstawionych rozwiązań, a także moją własną wersję rozwiązania w JavaScript. Poruszone są też niuanse każdego algorytmu.
Przypominamy: dla wszystkich czytelników „Habra” — zniżka 10 000 rubli przy zapisie na dowolny kurs Skillbox z kodem promocyjnym „Habra”.
Skillbox poleca: Praktyczny kurs .
Sformułowanie zadania
Dostajemy posortowaną tablicę i określoną wartość. Następnie prosimy o stworzenie funkcji, która zwraca true lub false, w zależności od tego, czy suma dowolnych dwóch liczb z tablicy może być równa podanej wartości.
Innymi słowy, czy w tablicy znajdują się dwie liczby całkowite x i y, które po dodaniu dają wskazaną wartość?
Przykład A
Jeśli mamy tablicę [1, 2, 4, 9] i wartość 8, funkcja zwróci false, ponieważ żadna para liczb z tablicy nie może dać 8 w sumie.
Przykład B
Jednak jeśli to będzie tablica [1, 2, 4, 4] i wartość 8, funkcja powinna zwrócić true, ponieważ 4 + 4 = 8.
Rozwiązanie 1. Bruteforce
Złożoność czasowa: O(N²).
Złożoność przestrzenna: O(1).
Najbardziej oczywistym podejściem jest użycie pary zagnieżdżonych pętli.
const findSum = (arr, val) => {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if (i !== j && arr[i] + arr[j] === val) {
return true;
};
};
};
return false;
};To rozwiązanie nie można nazwać efektywnym, ponieważ sprawdza każdą możliwą sumę dwóch elementów w tablicy, a także porównuje każdą parę indeksów dwukrotnie. (Na przykład, gdy i = 1 i j = 2 – to praktycznie to samo, co porównywanie z i = 2 i j = 1, ale w tym rozwiązaniu próbujemy oba warianty).
Ponieważ nasze rozwiązanie wykorzystuje parę zagnieżdżonych pętli for, ma kwadratową złożoność czasową O (N²).
Rozwiązanie 2. Wyszukiwanie binarne
Złożoność czasowa: O(Nlog(N)).
Złożoność przestrzenna: O(1).
Ponieważ tablice są posortowane, możemy poszukać rozwiązania przy użyciu wyszukiwania binarnego. Jest to najbardziej efektywny algorytm dla posortowanych tablic. Samo wyszukiwanie binarne ma czas wykonania O (log (N)). Niemniej jednak wciąż musimy użyć pętli for, aby sprawdzić każdy element w stosunku do wszystkich innych wartości.
Oto jak może wyglądać rozwiązanie. Aby wszystko było jasne, używamy osobnej funkcji do kontrolowania przeszukiwania binarnego. Ponadto funkcji removeIndex(), która zwraca wersję tablicy bez podanego indeksu.
const findSum = (arr, val) => {
for (let i = 0; i {
return arr.slice(0, i).concat(arr.slice(i + 1, arr.length));
};
const binarySearch = (arr, val) => {
let start = 0;
let end = arr.length - 1;
let pivot = Math.floor(arr.length / 2);
while (start < end) {
if (val arr[pivot]) {
start = pivot + 1;
};
pivot = Math.floor((start + end) / 2);
if (arr[pivot] === val) {
return true;
}
};
return false;
};Algorytm zaczyna od indeksu [0]. Następnie tworzy wersję tablicy, wykluczając pierwszy indeks, i używa przeszukiwania binarnego, aby sprawdzić, czy można dodać do tablicy jakąkolwiek z pozostałych wartości, aby uzyskać żądaną sumę. Działanie to wykonuje się raz dla każdego elementu tablicy.
Sam w sobie cykl for będzie miał liniową złożoność czasową O(N), ale wewnątrz cyklu for wykonujemy przeszukiwanie binarne, co daje ogólną złożoność czasową O(Nlog(N)). To rozwiązanie jest lepsze od poprzedniego, ale wciąż można je ulepszyć.
Rozwiązanie 3. Czas liniowy
Złożoność czasowa: O(N).
Złożoność przestrzenna: O(1).
Teraz rozwiążemy problem, pamiętając, że tablica jest posortowana. Rozwiązanie polega na wzięciu dwóch liczb: jednej na początku i jednej na końcu. Jeśli wynik różni się od wymaganego, zmieniamy punkt startowy i końcowy.
Na końcu albo napotkamy pożądaną wartość i zwrócimy true, albo punkty startowy i końcowy się zbiegną i zwrócimy false.
const findSum = (arr, val) => {
let start = 0;
let end = arr.length - 1;
while (start val) {
end -= 1;
} else if (sum < val) {
start += 1;
} else {
return true;
};
};
return false;
};Teraz wszystko jest w porządku, rozwiązanie wydaje się optymalne. Ale kto może zagwarantować, że tablica była uporządkowana?
Co wtedy?
Na pierwszy rzut oka moglibyśmy najpierw po prostu uporządkować tablicę, a następnie użyć powyższego rozwiązania. Ale jak wpłynie to na czas wykonania?
Najlepszy algorytm to szybkie sortowanie o złożoności czasowej O(Nlog(N)). Jeśli skorzystamy z niego w naszym optymalnym rozwiązaniu, zmieni to wydajność z O(N) na O(Nlog(N)). Czy można znaleźć liniowe rozwiązanie dla nieuporządkowanej tablicy?
Rozwiązanie 4
Złożoność czasowa: O(N).
Złożoność przestrzenna: O(N).
Tak, liniowe rozwiązanie istnieje, należy stworzyć nową tablicę zawierającą listę poszukiwań, które wykonujemy. Kompromis polega na bardziej aktywnym wykorzystaniu pamięci: to jedyne rozwiązanie w artykule o złożoności przestrzennej przekraczającej O(1).
Jeśli pierwsza wartość tej tablicy wynosi 1, a poszukiwana wartość wynosi 8, możemy dodać wartość 7 do tablicy 'wartości wyszukiwania'.
Następnie, przetwarzając każdy element tablicy, możemy sprawdzić tablicę 'wartości wyszukiwania' i zobaczyć, czy jedna z nich jest równa naszej wartości. Jeśli tak, zwracamy true.
const findSum = (arr, val) => {
let searchValues = [val - arr[0]];
for (let i = 1; i < arr.length; i++) {
let searchVal = val - arr[i];
if (searchValues.includes(arr[i])) {
return true;
} else {
searchValues.push(searchVal);
}
};
return false;
};Podstawą rozwiązania jest pętla for, która, jak widzieliśmy powyżej, ma liniową złożoność czasową O(N).
Drugą częścią iteracyjną naszej funkcji jest Array.prototype.include(), metoda JavaScript, która zwraca true lub false w zależności od tego, czy tablica zawiera daną wartość.
Aby ustalić złożoność czasową Array.prototype.includes(), możemy przyjrzeć się polyfillowi dostarczonemu przez MDN (napisanemu w JavaScript) lub skorzystać z metody w kodzie źródłowym silnika JavaScript, takiego jak Google V8 (C++).
// https://tc39.github.io/ecma262/#sec-array.prototype.includes
if (!Array.prototype.includes) {
Object.defineProperty(Array.prototype, 'includes', {
value: function(valueToFind, fromIndex) {
if (this == null) {
throw new TypeError('"this" is null or not defined');
}
// 1. Let O be ? ToObject(this value).
var o = Object(this);
// 2. Let len be ? ToLength(? Get(O, "length")).
var len = o.length >>> 0;
// 3. If len is 0, return false.
if (len === 0) {
return false;
}
// 4. Let n be ? ToInteger(fromIndex).
// (If fromIndex is undefined, this step produces the value 0.)
var n = fromIndex | 0;
// 5. If n ≥ 0, then
// a. Let k be n.
// 6. Else n < 0,
// a. Let k be len + n.
// b. If k < 0, let k be 0.
var k = Math.max(n >= 0 ? n : len - Math.abs(n), 0);
function sameValueZero(x, y) {
return x === y || (typeof x === 'number' && typeof y === 'number' && isNaN(x) && isNaN(y));
}
// 7. Repeat, while k < len
while (k < len) {
// a. Let elementK be the result of ? Get(O, ! ToString(k)).
// b. If SameValueZero(valueToFind, elementK) is true, return true.
if (sameValueZero(o[k], valueToFind)) {
return true;
}
// c. Increase k by 1.
k++;
}
// 8. Return false
return false;
}
});
}Część iteracyjna Array.prototype.include() to pętla while na kroku 7, która (prawie) pokrywa całą długość danej tablicy. Oznacza to, że jej złożoność czasowa również jest liniowa. Ponieważ zawsze jest o krok za naszym głównym zbiorem, złożoność czasowa wynosi O(N + (N - 1)). Korzystając z notacji Big O, upraszczamy ją do O(N) — ponieważ to N ma największy wpływ przy zwiększaniu wielkości wejściowej.
Jeśli chodzi o złożoność przestrzenną, potrzebna jest dodatkowa tablica, której długość odzwierciedla pierwotną tablicę (minus jeden, tak, ale można to zignorować), co prowadzi do złożoności przestrzennej O(N). Zwiększone wykorzystanie pamięci zapewnia maksymalną efektywność algorytmu.
Mam nadzieję, że artykuł okaże się dla Ciebie przydatny jako uzupełnienie do wywiadu wideo. Pokazuje, że proste zadanie może być rozwiązane na kilka różnych sposobów przy różnym wykorzystaniu zasobów (czas, pamięć).
Skillbox poleca:
- Kurs online .
- Kurs online .
- Praktyczny roczny kurs .
Źródło: habr.com
