Cześć! Dzisiejsza lekcja będzie nieco inna niż pozostałe. Różni się tym, że jest tylko pośrednio powiązany z Javą. To powiedziawszy, ten temat jest bardzo ważny dla każdego programisty. Będziemy rozmawiać o algorytmach . Co to jest algorytm? Mówiąc najprościej, jest to pewna sekwencja działań, które należy wykonać, aby osiągnąć pożądany rezultat . Algorytmów używamy często w życiu codziennym. Na przykład każdego ranka masz określone zadanie: iść do szkoły lub pracy, a jednocześnie być:
Ubrany
Czysty
Karmiony
Jaki algorytm pozwala osiągnąć taki wynik?
Obudź się za pomocą budzika.
Weź prysznic i umyj się.
Zrób śniadanie i kawę lub herbatę.
Jeść.
Jeśli poprzedniego wieczoru nie wyprasowałeś ubrań, wyprasuj je.
Ubrać się.
Opuścić dom.
Ta sekwencja działań z pewnością pozwoli uzyskać pożądany efekt. W programowaniu nieustannie pracujemy nad wykonaniem zadań. Znaczną część tych zadań można wykonać przy użyciu algorytmów, które są już znane. Załóżmy na przykład, że masz następujące zadanie: posortować listę 100 nazwisk w tablicy . To zadanie jest dość proste, ale można je rozwiązać na różne sposoby. Oto jedno z możliwych rozwiązań: Algorytm alfabetycznego sortowania nazw:
Kup lub pobierz wydanie Webster's Third New International Dictionary z 1961 roku.
Znajdź każde imię z naszej listy w tym słowniku.
Napisz na kartce stronę słownika, na której znajduje się nazwa.
Użyj kawałków papieru, aby posortować nazwy.
Czy taka sekwencja działań spełni nasze zadanie? Tak, z pewnością będzie. Czy to rozwiązanie jest wydajne ? Ledwie. Tutaj dochodzimy do kolejnego bardzo ważnego aspektu algorytmów: ich wydajności . Istnieje kilka sposobów wykonania tego zadania. Ale zarówno w programowaniu, jak iw codziennym życiu, chcemy wybrać najbardziej efektywną drogę. Jeśli twoim zadaniem jest zrobienie grzanki z masłem, możesz zacząć od zasiania pszenicy i wydojenia krowy. Ale to byłoby nieefektywnerozwiązanie — zajmie dużo czasu i będzie kosztować dużo pieniędzy. Możesz wykonać swoje proste zadanie, po prostu kupując chleb i masło. Chociaż pozwala rozwiązać problem, algorytm obejmujący pszenicę i krowę jest zbyt złożony, aby można go było zastosować w praktyce. W programowaniu mamy specjalną notację zwaną notacją dużego O do oceny złożoności algorytmów. Big O pozwala ocenić, jak bardzo czas wykonania algorytmu zależy od wielkości danych wejściowych . Spójrzmy na najprostszy przykład: transfer danych. Wyobraź sobie, że musisz przesłać pewne informacje w postaci pliku na dużą odległość (na przykład 5000 mil). Jaki algorytm byłby najbardziej wydajny? To zależy od danych, z którymi pracujesz. Załóżmy na przykład, że mamy plik audio o wielkości 10 MB. W takim przypadku najskuteczniejszym algorytmem jest przesłanie pliku przez Internet. To nie mogło zająć więcej niż kilka minut! Powtórzmy nasz algorytm: „Jeśli chcesz przesłać informacje w postaci plików na odległość 5000 mil, powinieneś przesłać dane przez Internet”. Doskonały. Teraz przeanalizujmy to. Czy spełnia nasze zadanie?Cóż, tak, tak. Ale co możemy powiedzieć o jego złożoności? Hmm, teraz robi się coraz ciekawiej. Faktem jest, że nasz algorytm jest bardzo zależny od danych wejściowych, a mianowicie od wielkości plików. Jeśli mamy 10 megabajtów, wszystko jest w porządku. Ale co, jeśli musimy wysłać 500 megabajtów? 20 gigabajtów? 500 terabajtów? 30 petabajtów? Czy nasz algorytm przestanie działać? Nie, wszystkie te ilości danych rzeczywiście można przenieść. Czy to potrwa dłużej? Tak, to będzie! Teraz znamy ważną cechę naszego algorytmu: im większa ilość danych do przesłania, tym dłużej zajmie wykonanie algorytmu. Chcielibyśmy jednak dokładniej zrozumieć tę zależność (między wielkością danych wejściowych a czasem potrzebnym do ich wysłania). W naszym przypadku złożoność algorytmiczna jest liniowa . „Liniowy” oznacza, że wraz ze wzrostem ilości danych wejściowych czas potrzebny na ich wysłanie wydłuży się w przybliżeniu proporcjonalnie. Jeśli ilość danych podwoi się, to czas potrzebny na ich przesłanie będzie dwukrotnie większy. Jeśli dane wzrosną 10-krotnie, to czas transmisji wzrośnie 10-krotnie. Używając notacji dużego O, złożoność naszego algorytmu wyraża się jako O(n). Powinieneś zapamiętać ten zapis na przyszłość — jest on zawsze używany dla algorytmów o złożoności liniowej. Zauważ, że nie mówimy tutaj o kilku rzeczach, które mogą się różnić: szybkości Internetu, mocy obliczeniowej naszego komputera i tak dalej. Oceniając złożoność algorytmu, po prostu nie ma sensu brać pod uwagę tych czynników — w każdym razie są one poza naszą kontrolą. Notacja Big O wyraża złożoność samego algorytmu, a nie „środowisko”, w którym działa. Kontynuujmy nasz przykład. Załóżmy, że ostatecznie dowiemy się, że musimy przesłać pliki o łącznej wielkości 800 terabajtów. Możemy oczywiście wykonać nasze zadanie, przesyłając je przez Internet. Jest tylko jeden problem: przy standardowej prędkości transmisji danych w gospodarstwie domowym (100 megabitów na sekundę) zajmie to około 708 dni. Prawie 2 lata! :O Nasz algorytm oczywiście nie pasuje tutaj. Potrzebujemy innego rozwiązania! Nieoczekiwanie z pomocą przychodzi nam gigant IT Amazon! Usługa Snowmobile firmy Amazon pozwala nam przesyłać duże ilości danych do pamięci mobilnej, a następnie dostarczać je pod wskazany adres ciężarówką! Mamy więc nowy algorytm! „Jeżeli chcesz przesłać informacje w postaci plików na odległość 5000 mil, a ich przesłanie przez Internet zajęłoby więcej niż 14 dni, powinieneś przesłać dane ciężarówką Amazona”. Wybraliśmy tu arbitralnie 14 dni. Powiedzmy, że jest to najdłuższy okres, na jaki możemy czekać. Przeanalizujmy nasz algorytm. A co z jego szybkością? Nawet jeśli ciężarówka porusza się z prędkością zaledwie 50 mil na godzinę, pokona 5000 mil w zaledwie 100 godzin. To trochę ponad cztery dni! Jest to o wiele lepsze niż możliwość przesyłania danych przez Internet. A co ze złożonością tego algorytmu? Czy też jest liniowy, czyli O(n)? Nie, nie jest. W końcu ciężarówka nie dba o to, jak mocno ją załadujesz — nadal będzie jechała mniej więcej z tą samą prędkością i dojedzie na czas. Niezależnie od tego, czy mamy 800 terabajtów, czy 10 razy więcej, ciężarówka i tak dotrze do celu w ciągu 5 dni. Innymi słowy, algorytm przesyłania danych oparty na ciężarówkach ma stałą złożoność. Tutaj „stała” oznacza, że nie zależy od rozmiaru danych wejściowych. Umieść pendrive o pojemności 1 GB w ciężarówce, dotrze w ciągu 5 dni. Włóż dyski zawierające 800 terabajtów danych, przyjdą w ciągu 5 dni. Gdy używamy notacji dużego O, stała złożoność jest oznaczana przez O(1) . Zapoznaliśmy się już z O(n) i O(1) , więc teraz spójrzmy na więcej przykładów ze świata programowania :) Załóżmy, że dostałeś tablicę 100 liczb, a zadaniem jest wyświetlenie każdej z nich na konsola. Piszesz zwykłą forpętlę, która wykonuje to zadanie
int[] numbers = new int[100];
// ...fill the array with numbers
for (int i: numbers) {
System.out.println(i);
}
Jaka jest złożoność tego algorytmu? Liniowy, tj. O(n). Liczba akcji, które program musi wykonać, zależy od liczby przekazanych mu liczb. Jeśli w tablicy jest 100 liczb, będzie 100 akcji (instrukcji do wyświetlenia napisów na ekranie). Jeśli w tablicy jest 10 000 liczb, należy wykonać 10 000 akcji. Czy nasz algorytm można w jakikolwiek sposób ulepszyć? Nie. Bez względu na wszystko, będziemy musieli wykonać N przejść przez tablicę i wykonać N instrukcji, aby wyświetlić ciągi znaków na konsoli. Rozważ inny przykład.
public static void main(String[] args) {
LinkedList<Integer> numbers = new LinkedList<>();
numbers.add(0, 20202);
numbers.add(0, 123);
numbers.add(0, 8283);
}
Mamy puste miejsce LinkedList, w które wstawiamy kilka liczb. Musimy ocenić złożoność algorytmiczną wstawiania pojedynczej liczby do liczby LinkedListw naszym przykładzie i jak zależy to od liczby elementów na liście. Odpowiedzią jest O(1), czyli stała złożoność . Dlaczego? Zauważ, że wstawiamy każdy numer na początku listy. Ponadto przypomnisz sobie, że po wstawieniu liczby do LinkedList, elementy nigdzie się nie przesuwają. Linki (lub odniesienia) są aktualizowane (jeśli zapomniałeś, jak działa LinkedList, spójrz na jedną z naszych starych lekcji ). Jeśli pierwszą liczbą na naszej liście jest x, a my wstawimy liczbę y na początku listy, to wszystko, co musimy zrobić, to:
x.previous = y;
y.previous = null;
y.next = x;
Kiedy aktualizujemy linki, nie obchodzi nas, ile liczb jest już wLinkedList , czy to jeden, czy miliard. Złożoność algorytmu jest stała, tj. O(1).
Złożoność logarytmiczna
Nie panikować! :) Jeśli słowo „logarytmiczny” sprawia, że chcesz zamknąć tę lekcję i przestać czytać, poczekaj kilka minut. Nie będzie tu żadnej szalonej matematyki (takich wyjaśnień jest mnóstwo gdzie indziej), a każdy przykład wybierzemy osobno. Wyobraź sobie, że Twoim zadaniem jest znalezienie jednej konkretnej liczby w tablicy 100 liczb. Dokładniej, musisz sprawdzić, czy tam jest, czy nie. Po znalezieniu wymaganej liczby wyszukiwanie kończy się, aw konsoli wyświetla się komunikat: „Znaleziono wymaganą liczbę! Jej indeks w tablicy =…” Jak wykonasz to zadanie? Tutaj rozwiązanie jest oczywiste: trzeba iterować po elementach tablicy jeden po drugim, zaczynając od pierwszego (lub od ostatniego) i sprawdzić, czy aktualna liczba odpowiada tej, której szukasz. Odpowiednio, liczba akcji zależy bezpośrednio od liczby elementów w tablicy. Jeśli mamy 100 liczb, potencjalnie musimy przejść do następnego elementu 100 razy i wykonać 100 porównań. Jeśli jest 1000 liczb, to może być 1000 porównań. Jest to oczywiście złożoność liniowa, tjO(n) . A teraz dodamy jedno uściślenie do naszego przykładu: tablica, w której należy znaleźć liczbę, jest posortowana rosnąco . Czy to coś zmienia w odniesieniu do naszego zadania? Nadal moglibyśmy przeprowadzić brutalne wyszukiwanie żądanej liczby. Ale alternatywnie moglibyśmy użyć dobrze znanego algorytmu wyszukiwania binarnego . W górnym rzędzie na obrazku widzimy posortowaną tablicę. Musimy znaleźć w nim liczbę 23. Zamiast iterować po liczbach, po prostu dzielimy tablicę na 2 części i sprawdzamy środkową liczbę w tablicy. Znajdź numer, który znajduje się w komórce 4 i sprawdź go (drugi rząd na obrazku). Ta liczba to 16, a my szukamy 23. Obecna liczba jest mniejsza niż ta, której szukamy. Co to znaczy? To znaczy, żewszystkie poprzednie liczby (te znajdujące się przed liczbą 16) nie muszą być sprawdzane : na pewno będą mniejsze niż ta, której szukamy, ponieważ nasza tablica jest posortowana! Kontynuujemy poszukiwania wśród pozostałych 5 elementów. Notatka:przeprowadziliśmy tylko jedno porównanie, ale wyeliminowaliśmy już połowę możliwych opcji. Zostało nam tylko 5 elementów. Powtórzymy nasz poprzedni krok, ponownie dzieląc pozostałą podtablicę na pół i ponownie biorąc środkowy element (trzeci rząd na obrazku). Liczba to 56 i jest większa niż ta, której szukamy. Co to znaczy? Oznacza to, że wyeliminowaliśmy kolejne 3 możliwości: samą liczbę 56 oraz dwie liczby następujące po niej (ponieważ na pewno są większe niż 23, ponieważ tablica jest posortowana). Pozostały nam tylko 2 liczby do sprawdzenia (ostatni wiersz na obrazku) — liczby z indeksami tablicy 5 i 6. Sprawdzamy pierwszą z nich i znajdujemy to, czego szukaliśmy — liczbę 23! Jego indeks wynosi 5! Spójrzmy na wyniki naszego algorytmu, a następnie przeanalizuję jego złożoność. Nawiasem mówiąc, teraz rozumiesz, dlaczego nazywa się to wyszukiwaniem binarnym: polega ono na wielokrotnym dzieleniu danych na pół. Wynik jest imponujący! Gdybyśmy użyli wyszukiwania liniowego do wyszukania liczby, potrzebowalibyśmy do 10 porównań, ale przy wyszukiwaniu binarnym wykonaliśmy zadanie z zaledwie 3! W najgorszym przypadku byłyby 4 porównania (jeśli w ostatnim kroku poszukiwana przez nas liczba była drugą z pozostałych możliwości, a nie pierwszą. A co z jej złożonością? To bardzo ciekawy punkt :) Algorytm wyszukiwania binarnego jest znacznie mniej zależny od liczby elementów w tablicy niż algorytm wyszukiwania liniowego (czyli prosta iteracja). Przy 10 elementach w tablicy wyszukiwanie liniowe będzie wymagało maksymalnie 10 porównań, ale wyszukiwanie binarne będzie wymagało maksymalnie 4 porównań. To różnica 2,5 razy. Ale dla tablicy 1000 elementów wyszukiwanie liniowe będzie wymagało do 1000 porównań, ale wyszukiwanie binarne wymagałoby tylko 10 ! Różnica jest teraz 100-krotna! Notatka:liczba elementów w tablicy wzrosła 100-krotnie (z 10 do 1000), ale liczba porównań wymaganych do wyszukiwania binarnego wzrosła tylko 2,5-krotnie (z 4 do 10). Jeśli dojdziemy do 10 000 elementów , różnica będzie jeszcze bardziej imponująca: 10 000 porównań dla wyszukiwania liniowego i łącznie 14 porównań dla wyszukiwania binarnego. I znowu, jeśli liczba elementów wzrośnie 1000 razy (z 10 do 10 000), to liczba porównań wzrośnie tylko o współczynnik 3,5 (z 4 do 14). Złożoność algorytmu wyszukiwania binarnego jest logarytmiczna lub, jeśli używamy notacji dużego O, O(log n). Dlaczego to się tak nazywa? Logarytm jest przeciwieństwem potęgowania. Logarytm binarny to potęga, do której należy podnieść liczbę 2, aby otrzymać liczbę. Na przykład mamy 10 000 elementów, które musimy przeszukać za pomocą algorytmu wyszukiwania binarnego. Obecnie możesz spojrzeć na tabelę wartości, aby wiedzieć, że będzie to wymagało maksymalnie 14 porównań. Ale co, jeśli nikt nie dostarczył takiej tabeli i musisz obliczyć dokładną maksymalną liczbę porównań? Wystarczy odpowiedzieć na proste pytanie: do jakiej potęgi należy podnieść liczbę 2, aby wynik był większy lub równy liczbie sprawdzanych elementów? Dla 10 000 jest to czternasta potęga. 2 do potęgi 13 to za mało (8192), ale 2 do potęgi 14 = 16384, a liczba ta spełnia nasz warunek (jest większa lub równa liczbie elementów w tablicy). Znaleźliśmy logarytm: 14. Tyle porównań możemy potrzebować! :) Algorytmy i złożoność algorytmiczna to zbyt szeroki temat, aby zmieścić się w jednej lekcji. Ale wiedza o tym jest bardzo ważna: wiele rozmów kwalifikacyjnych będzie dotyczyło pytań dotyczących algorytmów. Teoretycznie mogę ci polecić kilka książek. Możesz zacząć od „ Algorytmów grokkingowych ”. Przykłady w tej książce są napisane w Pythonie, ale w książce użyto bardzo prostego języka i przykładów. To najlepsza opcja dla początkującego, a do tego nie jest zbyt duża. Wśród bardziej poważnych lektur mamy książki Roberta Lafore'a i Roberta Sedgewicka. Oba są napisane w Javie, co ułatwi ci naukę. W końcu znasz ten język! :) Dla uczniów z dobrymi umiejętnościami matematycznymi najlepszą opcją jest książka Thomasa Cormena . Ale sama teoria nie napełni twojego brzucha! Wiedza ! = Zdolność . Możesz ćwiczyć rozwiązywanie problemów związanych z algorytmami na HackerRank i LeetCode . Zadania z tych stron są często wykorzystywane nawet podczas wywiadów w Google i Facebook, więc na pewno nie będziecie się nudzić :) Dla wzmocnienia materiału lekcyjnego polecam obejrzenie tego świetnego filmu o notacji dużego O na YouTube. Do zobaczenia na kolejnych lekcjach! :)
Artem is a programmer-switcher. His first profession was rehabilitation specialist. Previously, he helped people restore their hea ...
[Przeczytaj pełną biografię]
To powiedziawszy, ten temat jest bardzo ważny dla każdego programisty. Będziemy rozmawiać o algorytmach . Co to jest algorytm? Mówiąc najprościej, jest to pewna sekwencja działań, które należy wykonać, aby osiągnąć pożądany rezultat . Algorytmów używamy często w życiu codziennym. Na przykład każdego ranka masz określone zadanie: iść do szkoły lub pracy, a jednocześnie być:
W takim przypadku najskuteczniejszym algorytmem jest przesłanie pliku przez Internet. To nie mogło zająć więcej niż kilka minut! Powtórzmy nasz algorytm: „Jeśli chcesz przesłać informacje w postaci plików na odległość 5000 mil, powinieneś przesłać dane przez Internet”. Doskonały. Teraz przeanalizujmy to. Czy spełnia nasze zadanie?Cóż, tak, tak. Ale co możemy powiedzieć o jego złożoności? Hmm, teraz robi się coraz ciekawiej. Faktem jest, że nasz algorytm jest bardzo zależny od danych wejściowych, a mianowicie od wielkości plików. Jeśli mamy 10 megabajtów, wszystko jest w porządku. Ale co, jeśli musimy wysłać 500 megabajtów? 20 gigabajtów? 500 terabajtów? 30 petabajtów? Czy nasz algorytm przestanie działać? Nie, wszystkie te ilości danych rzeczywiście można przenieść. Czy to potrwa dłużej? Tak, to będzie! Teraz znamy ważną cechę naszego algorytmu: im większa ilość danych do przesłania, tym dłużej zajmie wykonanie algorytmu. Chcielibyśmy jednak dokładniej zrozumieć tę zależność (między wielkością danych wejściowych a czasem potrzebnym do ich wysłania). W naszym przypadku złożoność algorytmiczna jest liniowa . „Liniowy” oznacza, że wraz ze wzrostem ilości danych wejściowych czas potrzebny na ich wysłanie wydłuży się w przybliżeniu proporcjonalnie. Jeśli ilość danych podwoi się, to czas potrzebny na ich przesłanie będzie dwukrotnie większy. Jeśli dane wzrosną 10-krotnie, to czas transmisji wzrośnie 10-krotnie. Używając notacji dużego O, złożoność naszego algorytmu wyraża się jako O(n). Powinieneś zapamiętać ten zapis na przyszłość — jest on zawsze używany dla algorytmów o złożoności liniowej. Zauważ, że nie mówimy tutaj o kilku rzeczach, które mogą się różnić: szybkości Internetu, mocy obliczeniowej naszego komputera i tak dalej. Oceniając złożoność algorytmu, po prostu nie ma sensu brać pod uwagę tych czynników — w każdym razie są one poza naszą kontrolą. Notacja Big O wyraża złożoność samego algorytmu, a nie „środowisko”, w którym działa. Kontynuujmy nasz przykład. Załóżmy, że ostatecznie dowiemy się, że musimy przesłać pliki o łącznej wielkości 800 terabajtów. Możemy oczywiście wykonać nasze zadanie, przesyłając je przez Internet. Jest tylko jeden problem: przy standardowej prędkości transmisji danych w gospodarstwie domowym (100 megabitów na sekundę) zajmie to około 708 dni. Prawie 2 lata! :O Nasz algorytm oczywiście nie pasuje tutaj. Potrzebujemy innego rozwiązania! Nieoczekiwanie z pomocą przychodzi nam gigant IT Amazon! Usługa Snowmobile firmy Amazon pozwala nam przesyłać duże ilości danych do pamięci mobilnej, a następnie dostarczać je pod wskazany adres ciężarówką! 
Mamy więc nowy algorytm! „Jeżeli chcesz przesłać informacje w postaci plików na odległość 5000 mil, a ich przesłanie przez Internet zajęłoby więcej niż 14 dni, powinieneś przesłać dane ciężarówką Amazona”. Wybraliśmy tu arbitralnie 14 dni. Powiedzmy, że jest to najdłuższy okres, na jaki możemy czekać. Przeanalizujmy nasz algorytm. A co z jego szybkością? Nawet jeśli ciężarówka porusza się z prędkością zaledwie 50 mil na godzinę, pokona 5000 mil w zaledwie 100 godzin. To trochę ponad cztery dni! Jest to o wiele lepsze niż możliwość przesyłania danych przez Internet. A co ze złożonością tego algorytmu? Czy też jest liniowy, czyli O(n)? Nie, nie jest. W końcu ciężarówka nie dba o to, jak mocno ją załadujesz — nadal będzie jechała mniej więcej z tą samą prędkością i dojedzie na czas. Niezależnie od tego, czy mamy 800 terabajtów, czy 10 razy więcej, ciężarówka i tak dotrze do celu w ciągu 5 dni. Innymi słowy, algorytm przesyłania danych oparty na ciężarówkach ma stałą złożoność. Tutaj „stała” oznacza, że nie zależy od rozmiaru danych wejściowych. Umieść pendrive o pojemności 1 GB w ciężarówce, dotrze w ciągu 5 dni. Włóż dyski zawierające 800 terabajtów danych, przyjdą w ciągu 5 dni. Gdy używamy notacji dużego O, stała złożoność jest oznaczana przez O(1) . Zapoznaliśmy się już z O(n) i O(1) , więc teraz spójrzmy na więcej przykładów ze świata programowania :) Załóżmy, że dostałeś tablicę 100 liczb, a zadaniem jest wyświetlenie każdej z nich na konsola. Piszesz zwykłą 
W górnym rzędzie na obrazku widzimy posortowaną tablicę. Musimy znaleźć w nim liczbę 23. Zamiast iterować po liczbach, po prostu dzielimy tablicę na 2 części i sprawdzamy środkową liczbę w tablicy. Znajdź numer, który znajduje się w komórce 4 i sprawdź go (drugi rząd na obrazku). Ta liczba to 16, a my szukamy 23. Obecna liczba jest mniejsza niż ta, której szukamy. Co to znaczy? To znaczy, żewszystkie poprzednie liczby (te znajdujące się przed liczbą 16) nie muszą być sprawdzane : na pewno będą mniejsze niż ta, której szukamy, ponieważ nasza tablica jest posortowana! Kontynuujemy poszukiwania wśród pozostałych 5 elementów. Notatka:przeprowadziliśmy tylko jedno porównanie, ale wyeliminowaliśmy już połowę możliwych opcji. Zostało nam tylko 5 elementów. Powtórzymy nasz poprzedni krok, ponownie dzieląc pozostałą podtablicę na pół i ponownie biorąc środkowy element (trzeci rząd na obrazku). Liczba to 56 i jest większa niż ta, której szukamy. Co to znaczy? Oznacza to, że wyeliminowaliśmy kolejne 3 możliwości: samą liczbę 56 oraz dwie liczby następujące po niej (ponieważ na pewno są większe niż 23, ponieważ tablica jest posortowana). Pozostały nam tylko 2 liczby do sprawdzenia (ostatni wiersz na obrazku) — liczby z indeksami tablicy 5 i 6. Sprawdzamy pierwszą z nich i znajdujemy to, czego szukaliśmy — liczbę 23! Jego indeks wynosi 5! Spójrzmy na wyniki naszego algorytmu, a następnie przeanalizuję jego złożoność. Nawiasem mówiąc, teraz rozumiesz, dlaczego nazywa się to wyszukiwaniem binarnym: polega ono na wielokrotnym dzieleniu danych na pół. Wynik jest imponujący! Gdybyśmy użyli wyszukiwania liniowego do wyszukania liczby, potrzebowalibyśmy do 10 porównań, ale przy wyszukiwaniu binarnym wykonaliśmy zadanie z zaledwie 3! W najgorszym przypadku byłyby 4 porównania (jeśli w ostatnim kroku poszukiwana przez nas liczba była drugą z pozostałych możliwości, a nie pierwszą. A co z jej złożonością? To bardzo ciekawy punkt :) Algorytm wyszukiwania binarnego jest znacznie mniej zależny od liczby elementów w tablicy niż algorytm wyszukiwania liniowego (czyli prosta iteracja). Przy 10 elementach w tablicy wyszukiwanie liniowe będzie wymagało maksymalnie 10 porównań, ale wyszukiwanie binarne będzie wymagało maksymalnie 4 porównań. To różnica 2,5 razy. Ale dla tablicy 1000 elementów wyszukiwanie liniowe będzie wymagało do 1000 porównań, ale wyszukiwanie binarne wymagałoby tylko 10 ! Różnica jest teraz 100-krotna! Notatka:liczba elementów w tablicy wzrosła 100-krotnie (z 10 do 1000), ale liczba porównań wymaganych do wyszukiwania binarnego wzrosła tylko 2,5-krotnie (z 4 do 10). Jeśli dojdziemy do 10 000 elementów , różnica będzie jeszcze bardziej imponująca: 10 000 porównań dla wyszukiwania liniowego i łącznie 14 porównań dla wyszukiwania binarnego. I znowu, jeśli liczba elementów wzrośnie 1000 razy (z 10 do 10 000), to liczba porównań wzrośnie tylko o współczynnik 3,5 (z 4 do 14). Złożoność algorytmu wyszukiwania binarnego jest logarytmiczna lub, jeśli używamy notacji dużego O, O(log n). Dlaczego to się tak nazywa? Logarytm jest przeciwieństwem potęgowania. Logarytm binarny to potęga, do której należy podnieść liczbę 2, aby otrzymać liczbę. Na przykład mamy 10 000 elementów, które musimy przeszukać za pomocą algorytmu wyszukiwania binarnego. 
Obecnie możesz spojrzeć na tabelę wartości, aby wiedzieć, że będzie to wymagało maksymalnie 14 porównań. Ale co, jeśli nikt nie dostarczył takiej tabeli i musisz obliczyć dokładną maksymalną liczbę porównań? Wystarczy odpowiedzieć na proste pytanie: do jakiej potęgi należy podnieść liczbę 2, aby wynik był większy lub równy liczbie sprawdzanych elementów? Dla 10 000 jest to czternasta potęga. 2 do potęgi 13 to za mało (8192), ale 2 do potęgi 14 = 16384, a liczba ta spełnia nasz warunek (jest większa lub równa liczbie elementów w tablicy). Znaleźliśmy logarytm: 14. Tyle porównań możemy potrzebować! :) Algorytmy i złożoność algorytmiczna to zbyt szeroki temat, aby zmieścić się w jednej lekcji. Ale wiedza o tym jest bardzo ważna: wiele rozmów kwalifikacyjnych będzie dotyczyło pytań dotyczących algorytmów. Teoretycznie mogę ci polecić kilka książek. Możesz zacząć od „ Algorytmów grokkingowych ”. Przykłady w tej książce są napisane w Pythonie, ale w książce użyto bardzo prostego języka i przykładów. To najlepsza opcja dla początkującego, a do tego nie jest zbyt duża. Wśród bardziej poważnych lektur mamy książki Roberta Lafore'a i Roberta Sedgewicka. Oba są napisane w Javie, co ułatwi ci naukę. W końcu znasz ten język! :) Dla uczniów z dobrymi umiejętnościami matematycznymi najlepszą opcją jest książka Thomasa Cormena . Ale sama teoria nie napełni twojego brzucha! Wiedza ! = Zdolność . Możesz ćwiczyć rozwiązywanie problemów związanych z algorytmami na HackerRank i LeetCode . Zadania z tych stron są często wykorzystywane nawet podczas wywiadów w Google i Facebook, więc na pewno nie będziecie się nudzić :) Dla wzmocnienia materiału lekcyjnego polecam obejrzenie tego świetnego filmu o notacji dużego O na YouTube. Do zobaczenia na kolejnych lekcjach! :)
GO TO FULL VERSION