Kiedy badałem działanie algorytmów, natknąłem się na to . Nie tylko daje wyobrażenie o tym, jak przeprowadzane są rozmowy kwalifikacyjne w dużych korporacjach technologicznych, ale także pozwala zrozumieć, w jaki sposób problemy algorytmiczne są rozwiązywane w możliwie najefektywniejszy sposób.
Ten artykuł jest swego rodzaju dodatkiem do filmu. Przedstawiam w nim komentarze do wszystkich pokazanych rozwiązań oraz moją własną wersję rozwiązania w JavaScript. Omówiono także niuanse każdego algorytmu.
Przypomnienie: dla wszystkich czytelników „Habr” - rabat w wysokości 10 000 rubli przy zapisywaniu się na dowolny kurs Skillbox przy użyciu kodu promocyjnego „Habr”.
Skillbox poleca: Kurs praktyczny .
Stwierdzenie problemu
Otrzymujemy uporządkowaną tablicę i określoną wartość. Następnie proszone jest o utworzenie funkcji, która zwróci prawdę lub fałsz w zależności od tego, czy suma dowolnych dwóch liczb w tablicy może być równa danej wartości.
Innymi słowy, czy w tablicy znajdują się dwie liczby całkowite, x i y, które po dodaniu dają określoną wartość?
Przykład A
Jeśli otrzymamy tablicę [1, 2, 4, 9], a jej wartość wynosi 8, funkcja zwróci wartość false, ponieważ żadne dwie liczby w tablicy nie mogą sumować się do 8.
Przykład B
Ale jeśli jest to tablica [1, 2, 4, 4] i wartość wynosi 8, funkcja powinna zwrócić wartość true, ponieważ 4 + 4 = 8.
Rozwiązanie 1: Brutalna siła
Złożoność czasowa: O(N²).
Złożoność przestrzenna: O(1).
Najbardziej oczywistym znaczeniem 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 jest wydajne, ponieważ sprawdza każdą możliwą sumę dwóch elementów tablicy, a także dwukrotnie porównuje każdą parę indeksów. (Na przykład, gdy i = 1 i j = 2 jest w rzeczywistości tym samym, co porównanie z i = 2 i j = 1, ale w tym rozwiązaniu wypróbowujemy obie opcje).
Ponieważ nasze rozwiązanie wykorzystuje parę zagnieżdżonych pętli for, jest kwadratowe ze złożonością czasową O(N²).
Rozwiązanie 2: Wyszukiwanie binarne
Złożoność czasowa: O(Nlog(N)).
Złożoność przestrzenna: O(1).
Ponieważ tablice są uporządkowane, możemy szukać rozwiązania za pomocą wyszukiwania binarnego. Jest to najbardziej efektywny algorytm dla tablic uporządkowanych. Samo wyszukiwanie binarne ma czas działania O(log(N)). Jednak nadal musisz użyć pętli for, aby sprawdzić każdy element pod kątem wszystkich innych wartości.
Oto jak może wyglądać rozwiązanie. Aby było jasne, używamy osobnej funkcji do sterowania wyszukiwaniem binarnym. A także funkcja usuwaniaIndex(), która zwraca wersję tablicy pomniejszoną o podany indeks.
const findSum = (arr, val) => {
for (let i = 0; i < arr.length; i++){
if (binarySearch(removeIndex(arr, i), val - arr[i])) {
return true;
}
};
return false;
};
const removeIndex = (arr, 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]) {
end = pivot - 1;
} else if (val > arr[pivot]) {
start = pivot + 1;
};
pivot = Math.floor((start + end) / 2);
if (arr[pivot] === val) {
return true;
}
};
return false;
};Algorytm rozpoczyna się od indeksu [0]. Następnie tworzy wersję tablicy z wyłączeniem pierwszego indeksu i wykorzystuje wyszukiwanie binarne, aby sprawdzić, czy którąś z pozostałych wartości można dodać do tablicy, aby uzyskać żądaną sumę. Ta akcja jest wykonywana raz dla każdego elementu tablicy.
Sama pętla for będzie miała liniową złożoność czasową O(N), ale wewnątrz pętli for przeprowadzamy wyszukiwanie binarne, co daje całkowitą złożoność czasową O(Nlog(N)). To rozwiązanie jest lepsze od poprzedniego, ale wciąż jest nad czym pracować.
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ązaniem jest wzięcie dwóch liczb: jednej na początku i jednej na końcu. Jeśli wynik różni się od wymaganego, zmień punkt początkowy i końcowy.
Ostatecznie albo napotkamy żądaną wartość i zwrócimy wartość true, albo punkty początkowy i końcowy zbiegną się i zwrócimy false.
const findSum = (arr, val) => {
let start = 0;
let end = arr.length - 1;
while (start < end) {
let sum = arr[start] + arr[end];
if (sum > 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 została zamówiona?
Co wtedy?
Na pierwszy rzut oka mogliśmy po prostu zamówić najpierw macierz, a następnie zastosować powyższe rozwiązanie. Ale jak wpłynie to na czas wykonania?
Najlepszym algorytmem jest szybkie sortowanie ze złożonością czasową O (Nlog (N)). Jeśli użyjemy go w naszym optymalnym rozwiązaniu, zmieni on swoje działanie z O(N) na O(Nlog(N)). Czy można znaleźć rozwiązanie liniowe z tablicą nieuporządkowaną?
Rozwiązanie 4
Złożoność czasowa: O(N).
Złożoność przestrzenna: O(N).
Tak, istnieje rozwiązanie liniowe; w tym celu musimy utworzyć nową tablicę zawierającą listę szukanych dopasowań. Kompromisem jest większe wykorzystanie pamięci: jest to jedyne rozwiązanie w artykule o złożoności przestrzennej większej niż O(1).
Jeśli pierwszą wartością danej tablicy jest 1, a szukaną wartością jest 8, możemy dodać wartość 7 do tablicy „wyszukiwanych wartości”.
Następnie, przetwarzając każdy element tablicy, możemy sprawdzić tablicę „wyszukiwanych wartości” i sprawdzić, czy któraś z nich jest równa naszej wartości. Jeśli tak, zwróć wartość 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ą iteracyjną częścią naszej funkcji jest Array.prototype.include(), metoda JavaScript, która zwraca wartość true lub false w zależności od tego, czy tablica zawiera podaną wartość.
Aby obliczyć złożoność czasową Array.prototype.includes(), możemy przyjrzeć się wypełnieniu dostarczonemu przez MDN (i napisanemu w JavaScript) lub użyć 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;
}
});
}Tutaj iteracyjną częścią Array.prototype.include() jest pętla while z kroku 7, która (prawie) przechodzi przez całą długość danej tablicy. Oznacza to, że jego złożoność czasowa jest również liniowa. Cóż, ponieważ jest zawsze o krok za naszą główną tablicą, złożoność czasowa wynosi O (N + (N - 1)). Używając notacji Big O, upraszczamy to do O(N) - ponieważ to N ma największy wpływ na zwiększanie rozmiaru wejściowego.
Jeśli chodzi o złożoność przestrzenną, potrzebna jest dodatkowa tablica, której długość odzwierciedla oryginalną tablicę (minus jeden, tak, ale można to zignorować), co skutkuje złożonością przestrzenną O(N). Cóż, zwiększone wykorzystanie pamięci zapewnia maksymalną wydajność algorytmu.
Mam nadzieję, że artykuł okaże się przydatny jako uzupełnienie wywiadu wideo. Pokazuje, że prosty problem można rozwiązać na kilka różnych sposobów przy różnej ilości wykorzystanych zasobów (czasu, pamięci).
Skillbox poleca:
- Stosowany kurs online .
- Kurs online .
- Praktyczny roczny kurs .
Źródło: www.habr.com