Cześć! Dzisiejszy wykład będzie nieco inny od pozostałych. Będzie się różnić tym, że jest tylko pośrednio powiązany z Javą. Temat ten jest jednak bardzo ważny dla każdego programisty. Porozmawiamy 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 . Często używamy algorytmów w życiu codziennym. Na przykład każdego ranka stajesz przed zadaniem: przyjść do szkoły lub pracy, a jednocześnie być:
Ubrany
Czysty
Dobrze dokarmiony
Jaki algorytm pozwoli Ci osiągnąć taki wynik?
Obudź się przy budziku.
Weź prysznic, umyj twarz.
Przygotuj śniadanie, zaparz kawę/herbatę.
Jeść.
Jeśli nie prasowałeś ubrań od wieczora, wyprasuj je.
Ubrać się.
Opuścić dom.
Ta sekwencja działań z pewnością pozwoli Ci uzyskać pożądany rezultat. W programowaniu cały sens naszej pracy polega na ciągłym rozwiązywaniu problemów. Znaczącą część tych zadań można wykonać wykorzystując znane już algorytmy. Na przykład stoisz przed zadaniem: posortować listę 100 nazw w tablicy . Problem ten jest dość prosty, ale można go rozwiązać na różne sposoby. Oto jedno rozwiązanie: Algorytm sortowania nazw alfabetycznie:
Kup lub pobierz w Internecie „Słownik rosyjskich imion osobistych” wydanie z 1966 r.
Znajdź w tym słowniku każde imię z naszej listy.
Zapisz na kartce papieru, na której stronie słownika znajduje się dane imię.
Uporządkuj nazwy, korzystając z notatek na kartce papieru.
Czy taka sekwencja działań pozwoli nam rozwiązać nasz problem? Tak, całkowicie na to pozwoli. Czy to rozwiązanie będzie skuteczne ? Ledwie. Tutaj dochodzimy do kolejnej bardzo ważnej właściwości algorytmów – ich wydajności . Problem można rozwiązać na różne sposoby. Ale zarówno w programowaniu, jak i w życiu codziennym wybieramy metodę, która będzie najskuteczniejsza. Jeśli Twoim zadaniem jest zrobienie kanapki z masłem, możesz oczywiście zacząć od zasiania pszenicy i wydojenia krowy. Będzie to jednak rozwiązanie nieefektywne – zajmie dużo czasu i będzie kosztować dużo pieniędzy. Aby rozwiązać swój prosty problem, możesz po prostu kupić chleb i masło. A algorytm z pszenicą i krową, choć pozwala rozwiązać problem, jest zbyt skomplikowany, aby zastosować go w praktyce. Aby ocenić złożoność algorytmów w programowaniu, stworzono specjalną notację zwaną Big-O („big O”) . Big-O pozwala oszacować, w jakim stopniu czas wykonania algorytmu zależy od przekazanych do niego danych . Spójrzmy na najprostszy przykład – transfer danych. Wyobraź sobie, że musisz przesłać jakąś informację w formie pliku na dużą odległość (na przykład 5000 kilometrów). Który algorytm będzie najskuteczniejszy? To zależy od danych, z którymi musi pracować. Na przykład mamy plik audio o rozmiarze 10 megabajtów. W tym przypadku najskuteczniejszym algorytmem byłoby przesłanie pliku przez Internet. Zajmie to tylko kilka minut! Wypowiedzmy więc jeszcze raz nasz algorytm: „Jeśli chcesz przesłać informacje w postaci plików na odległość 5000 kilometrów, musisz skorzystać z transmisji danych przez Internet”. Świetnie. Teraz przeanalizujmy to. Czy to rozwiązuje nasz problem? Ogólnie tak, całkowicie to rozwiązuje. Ale co możesz powiedzieć o jego złożoności? Hmm, teraz sprawa robi się interesująca. Faktem jest, że nasz algorytm w dużej mierze zależy od napływających danych, a mianowicie od rozmiaru plików. Teraz mamy 10 megabajtów i wszystko jest w porządku. A co jeśli będziemy musieli przesł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 nadal można przesyłać. Czy ukończenie zajmie więcej czasu? Tak, to będzie! Teraz znamy ważną cechę naszego algorytmu: im większy rozmiar danych do przesłania, tym dłużej trwa algorytm . Chcielibyśmy jednak dokładniej zrozumieć, jak wygląda ta zależność (pomiędzy wielkością danych a czasem potrzebnym na ich przesłanie). W naszym przypadku złożoność algorytmu będzie liniowa. „Liniowy” oznacza, że wraz ze wzrostem objętości danych czas ich transmisji będzie się wydłużał w przybliżeniu proporcjonalnie. Jeśli danych jest 2 razy więcej, a ich przesłanie zajmie 2 razy więcej czasu. Jeśli danych jest 10 razy więcej, czas przesyłania wzrośnie 10 razy. Używając notacji Big-O, złożoność naszego algorytmu definiuje się jako O(N) . Tę notację najlepiej zapamiętać na przyszłość; jest ona zawsze używana w przypadku algorytmów o złożoności liniowej. Uwaga: wcale nie mówimy tutaj o różnych „zmiennych” rzeczach: szybkości Internetu, mocy naszego komputera i tak dalej. Oceniając złożoność algorytmu, to po prostu nie ma sensu – i tak nie mamy na to wpływu. Big-O ocenia sam algorytm, niezależnie od „środowiska”, w którym będzie musiał pracować. Kontynuujmy nasz przykład. Załóżmy, że ostatecznie okaże się, że rozmiar plików do przesłania wynosi 800 terabajtów. Jeśli prześlemy je przez Internet, problem oczywiście zostanie rozwiązany. Jest tylko jeden problem: transmisja po standardowym, nowoczesnym łączu (100 megabitów na sekundę), z którego większość z nas korzysta w domach, zajmie około 708 dni. Prawie 2 lata! :O Zatem nasz algorytm najwyraźniej nie jest tutaj odpowiedni. Potrzebujemy innego rozwiązania! Nagle z pomocą przychodzi nam gigant IT Amazon! Usługa Amazon Snowmobile pozwala załadować duże ilości danych do mobilnych jednostek magazynujących i dostarczyć je pod wskazany adres ciężarówką! Mamy więc nowy algorytm! „Jeśli potrzebujesz przesłać informacje w formie plików na odległość 5000 kilometrów, a w przypadku przesyłania przez Internet proces ten będzie trwał dłużej niż 14 dni, warto skorzystać z transportu ciężarowego Amazon.” Liczba 14 dni została tu wybrana losowo: powiedzmy, że jest to maksymalny okres, na jaki nas stać. Przeanalizujmy nasz algorytm. A co z prędkością? Nawet jeśli ciężarówka jedzie z prędkością zaledwie 50 km/h, 5000 kilometrów pokona w zaledwie 100 godzin. To nieco ponad cztery dni! Jest to znacznie lepsze rozwiązanie niż opcja transmisji internetowej. A co ze złożonością tego algorytmu? Czy będzie to również liniowe, O(N)? Nie, nie będzie. W końcu ciężarówka nie dba o to, ile ją załadujesz - nadal będzie jechała z mniej więcej tą samą prędkością i dotrze na czas. Niezależnie od tego, czy mamy 800 terabajtów, czy 10 razy więcej danych, ciężarówka i tak dotrze tam w 5 dni. Innymi słowy, algorytm dostarczania danych ciężarówką ma stałą złożoność . „Stała” oznacza, że nie jest ona zależna od danych przekazywanych do algorytmu. Włóż do ciężarówki pendrive o pojemności 1 GB, a przyjedzie w ciągu 5 dni. Umieść tam dyski z 800 terabajtami danych, a przyjdą za 5 dni. Podczas korzystania z Big-O stałą złożoność oznacza się jako O(1) . Odkąd poznaliśmy O(N) iO(1) , spójrzmy teraz na więcej przykładów „programistycznych” :) Załóżmy, że masz tablicę 100 liczb i zadaniem jest wydrukowanie każdej z nich na konsoli. Piszesz zwykłą pętlę for, która wykonuje to zadanie
Jaka jest złożoność zapisanego algorytmu? Liniowy, O(N). Liczba akcji, które program musi wykonać, zależy od tego, ile dokładnie liczb zostało do niego przekazanych. Jeśli w tablicy będzie 100 liczb, będzie 100 akcji (wyjście na ekranie).Jeśli w tablicy będzie 10 000 liczb, trzeba będzie wykonać 10 000 akcji. Czy można ulepszyć nasz algorytm? NIE. W każdym razie będziemy musieli wykonać N przejść przez tablicę i wykonać N wyjść na konsolę. Spójrzmy na inny przykład.
Mamy pusty LinkedList, do którego wstawiamy kilka liczb. Musimy oszacować złożoność algorytmu wstawiania pojedynczej liczby do LinkedListnaszego przykładu i to, jak zależy to od liczby elementów na liście. Odpowiedź brzmi O(1) – stała złożoność . Dlaczego? Uwaga: każdorazowo wstawiamy cyfrę na początku listy. Dodatkowo, jak pamiętacie, wstawiając liczby do LinkedListelementów, nie są one nigdzie przesuwane - linki są na nowo definiowane (jeśli nagle zapomnieliście, jak działa LinkedList, obejrzyjcie jeden z naszych starych wykładów ). Jeśli teraz pierwszą liczbą na naszej liście jest liczba х, a na początku listy wstawimy liczbę y, wystarczy:
x.previous = y;
y.previous =null;
y.next = x;
Dla tej redefinicji odniesienia nie ma dla nas znaczenia, ile jest teraz liczbLinkedList - przynajmniej jedna, co najmniej miliard. Złożoność algorytmu będzie stała - O(1).
Złożoność logarytmiczna
Nie panikować! :) Jeśli słowo „logarytmiczny” sprawia, że chcesz zamknąć wykład i nie czytać dalej, poczekaj kilka minut. Nie będzie tu żadnych trudności matematycznych (jest mnóstwo takich wyjaśnień w innych miejscach), a wszystkie przykłady przeanalizujemy „na palcach”. Wyobraź sobie, że Twoim zadaniem jest znalezienie jednej konkretnej liczby w tablicy składającej się ze 100 liczb. A dokładniej sprawdź, czy w ogóle tam jest. Po znalezieniu żądanego numeru należy przerwać wyszukiwanie, a w konsoli powinien wyświetlić się wpis „Znaleziono żądany numer!”. Jego indeks w tablicy =...”. Jak rozwiązałbyś taki problem? Tutaj rozwiązanie jest oczywiste: należy iterować po elementach tablicy, zaczynając od pierwszego (lub ostatniego) i sprawdzać, czy aktualna liczba pokrywa się z żądaną. W związku z tym liczba działań zależy bezpośrednio od liczby elementów w tablicy. Jeśli mamy 100 liczb, musimy 100 razy przejść do następnego elementu i 100 razy sprawdzić liczbę. Jeśli jest 1000 liczb, wówczas będzie 1000 kroków kontrolnych. Jest to oczywiście złożoność liniowa, O(N) . Teraz dodamy jedno wyjaśnienie do naszego przykładu: tablica, w której należy znaleźć liczbę, jest posortowana w kolejności rosnącej . Czy to coś zmienia dla naszego zadania? Nadal możemy wyszukać żądany numer brutalną siłą. Zamiast tego możemy jednak użyć dobrze znanego algorytmu wyszukiwania binarnego . W górnym wierszu obrazu widzimy posortowaną tablicę. Musimy w nim znaleźć liczbę 23. Zamiast iterować po liczbach, po prostu dzielimy tablicę na 2 części i sprawdzamy średnią liczbę w tablicy. Znajdujemy liczbę znajdującą się w komórce 4 i sprawdzamy ją (drugi rząd na obrazku). Ta liczba to 16, a my szukamy 23. Obecna liczba jest mniejsza. Co to znaczy? Że nie trzeba sprawdzać wszystkich poprzednich liczb (które znajdują się aż do liczby 16) : na pewno będą mniejsze od tej, której szukamy, ponieważ nasza tablica jest posortowana! Kontynuujmy poszukiwania wśród pozostałych 5 elementów. Zwróć uwagę:Przeprowadziliśmy tylko jedno sprawdzenie, ale wyeliminowaliśmy już połowę możliwych opcji. Zostało nam już tylko 5 elementów. Powtórzymy nasz krok - ponownie podziel pozostałą tablicę przez 2 i ponownie weź środkowy element (linia 3 na rysunku). Ta liczba wynosi 56 i jest większa niż ta, której szukamy. Co to znaczy? Że odrzucimy jeszcze 3 opcje - samą liczbę 56 i dwie liczby po niej (są zdecydowanie większe niż 23, ponieważ tablica jest posortowana). Do sprawdzenia pozostały nam już tylko 2 liczby (ostatni wiersz na rysunku) - liczby z indeksami tablicy 5 i 6. Sprawdzamy pierwszą z nich i właśnie tego szukaliśmy - liczby 23! Jego indeks = 5! Przyjrzyjmy się wynikom naszego algorytmu, a wtedy zrozumiemy jego złożoność. (Nawiasem mówiąc, teraz rozumiesz, dlaczego nazywa się to binarnym: jego istotą jest ciągłe dzielenie danych przez 2). Wynik jest imponujący! Gdybyśmy szukali żądanej liczby za pomocą wyszukiwania liniowego, potrzebowalibyśmy 10 kontroli, ale przy wyszukiwaniu binarnym zrobiliśmy to w 3! W najgorszym przypadku byłoby ich 4, gdyby na ostatnim etapie potrzebna nam liczba okazała się drugą, a nie pierwszą. A co z jego złożonością? To bardzo interesująca kwestia :) Algorytm wyszukiwania binarnego zależy w znacznie mniejszym stopniu od liczby elementów w tablicy niż algorytm wyszukiwania liniowego (czyli prostego wyliczenia). Przy 10 elementach w tablicy wyszukiwanie liniowe będzie wymagało maksymalnie 10 kontroli, a wyszukiwanie binarne będzie wymagało maksymalnie 4 kontroli. Różnica jest 2,5 razy. Ale w przypadku tablicy zawierającej 1000 elementów wyszukiwanie liniowe będzie wymagało 1000 kontroli, a wyszukiwanie binarne będzie wymagało tylko 10 ! Różnica jest już 100-krotna! Zwróć uwagę:liczba elementów tablicy wzrosła 100-krotnie (z 10 do 1000), a liczba niezbędnych sprawdzeń dla 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 sprawdza wyszukiwanie liniowe i łącznie 14 sprawdza w przypadku wyszukiwania binarnego. I znowu: liczba elementów wzrosła 1000 razy (z 10 do 10 000), ale liczba kontroli wzrosła tylko 3,5 razy (z 4 do 14). Złożoność algorytmu wyszukiwania binarnego jest logarytmiczna lub w notacji Big-O O(log n) . Dlaczego tak się nazywa? Logarytm jest odwrotnością potęgowania. Logarytm binarny służy do obliczania potęgi liczby 2. Na przykład mamy 10 000 elementów, które musimy sprawdzić za pomocą wyszukiwania binarnego. Teraz masz obraz przed oczami i wiesz, że wymaga to maksymalnie 14 kontroli. Ale co, jeśli nie masz obrazu przed oczami i musisz policzyć dokładną liczbę niezbędnych kontroli? Wystarczy odpowiedzieć na proste pytanie: do jakiej potęgi należy podnieść liczbę 2, aby otrzymany wynik był >= liczba sprawdzanych elementów? Dla 10000 będzie to potęga 14. 2 do potęgi 13 to za mało (8192) Ale 2 do potęgi 14 = 16384 to liczba spełniająca nasz warunek (jest to >= liczba elementów w tablicy). Znaleźliśmy logarytm - 14. Tyle kontroli potrzebujemy! :) Algorytmy i ich złożoność to temat zbyt obszerny, aby ująć go w jednym wykładzie. Ale wiedza o tym jest bardzo ważna: w wielu rozmowach kwalifikacyjnych pojawią się problemy algorytmiczne. Dla teorii mogę polecić Ci kilka książek. Dobrym miejscem na rozpoczęcie jest „ Algorytmy grockingu ”: chociaż przykłady w tej książce są napisane w języku Python, język książki i przykłady są bardzo proste. Najlepsza opcja dla początkującego, a także ma niewielką objętość. Poważniejsza lektura: książki Roberta Laforeta i Roberta Sedgwicka . Obydwa są napisane w Javie, co ułatwi Ci naukę. W końcu doskonale znasz ten język! :) Dla studentów z dobrym przygotowaniem matematycznym najlepszą opcją będzie książka Thomasa Cormana . Ale nie zadowoli Cię tylko teoria! „Wiedzieć” != „być w stanie” Możesz poćwiczyć rozwiązywanie problemów algorytmicznych w HackerRank i Leetcode . Zadania stamtąd są często wykorzystywane nawet podczas rozmów kwalifikacyjnych w Google i Facebooku, więc na pewno nie będziesz się nudzić :) Dla utrwalenia materiału z wykładu radzę obejrzeć świetny film o Big-O na YouTube. Do zobaczenia na kolejnych wykładach! :)
W tym przypadku najskuteczniejszym algorytmem byłoby przesłanie pliku przez Internet. Zajmie to tylko kilka minut! Wypowiedzmy więc jeszcze raz nasz algorytm: „Jeśli chcesz przesłać informacje w postaci plików na odległość 5000 kilometrów, musisz skorzystać z transmisji danych przez Internet”. Świetnie. Teraz przeanalizujmy to. Czy to rozwiązuje nasz problem? Ogólnie tak, całkowicie to rozwiązuje. Ale co możesz powiedzieć o jego złożoności? Hmm, teraz sprawa robi się interesująca. Faktem jest, że nasz algorytm w dużej mierze zależy od napływających danych, a mianowicie od rozmiaru plików. Teraz mamy 10 megabajtów i wszystko jest w porządku. A co jeśli będziemy musieli przesł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 nadal można przesyłać. Czy ukończenie zajmie więcej czasu? Tak, to będzie! Teraz znamy ważną cechę naszego algorytmu: im większy rozmiar danych do przesłania, tym dłużej trwa algorytm . Chcielibyśmy jednak dokładniej zrozumieć, jak wygląda ta zależność (pomiędzy wielkością danych a czasem potrzebnym na ich przesłanie). W naszym przypadku złożoność algorytmu będzie liniowa. „Liniowy” oznacza, że wraz ze wzrostem objętości danych czas ich transmisji będzie się wydłużał w przybliżeniu proporcjonalnie. Jeśli danych jest 2 razy więcej, a ich przesłanie zajmie 2 razy więcej czasu. Jeśli danych jest 10 razy więcej, czas przesyłania wzrośnie 10 razy. Używając notacji Big-O, złożoność naszego algorytmu definiuje się jako O(N) . Tę notację najlepiej zapamiętać na przyszłość; jest ona zawsze używana w przypadku algorytmów o złożoności liniowej. Uwaga: wcale nie mówimy tutaj o różnych „zmiennych” rzeczach: szybkości Internetu, mocy naszego komputera i tak dalej. Oceniając złożoność algorytmu, to po prostu nie ma sensu – i tak nie mamy na to wpływu. Big-O ocenia sam algorytm, niezależnie od „środowiska”, w którym będzie musiał pracować. Kontynuujmy nasz przykład. Załóżmy, że ostatecznie okaże się, że rozmiar plików do przesłania wynosi 800 terabajtów. Jeśli prześlemy je przez Internet, problem oczywiście zostanie rozwiązany. Jest tylko jeden problem: transmisja po standardowym, nowoczesnym łączu (100 megabitów na sekundę), z którego większość z nas korzysta w domach, zajmie około 708 dni. Prawie 2 lata! :O Zatem nasz algorytm najwyraźniej nie jest tutaj odpowiedni. Potrzebujemy innego rozwiązania! Nagle z pomocą przychodzi nam gigant IT Amazon! Usługa Amazon Snowmobile pozwala załadować duże ilości danych do mobilnych jednostek magazynujących i dostarczyć je pod wskazany adres ciężarówką! 
Mamy więc nowy algorytm! „Jeśli potrzebujesz przesłać informacje w formie plików na odległość 5000 kilometrów, a w przypadku przesyłania przez Internet proces ten będzie trwał dłużej niż 14 dni, warto skorzystać z transportu ciężarowego Amazon.” Liczba 14 dni została tu wybrana losowo: powiedzmy, że jest to maksymalny okres, na jaki nas stać. Przeanalizujmy nasz algorytm. A co z prędkością? Nawet jeśli ciężarówka jedzie z prędkością zaledwie 50 km/h, 5000 kilometrów pokona w zaledwie 100 godzin. To nieco ponad cztery dni! Jest to znacznie lepsze rozwiązanie niż opcja transmisji internetowej. A co ze złożonością tego algorytmu? Czy będzie to również liniowe, O(N)? Nie, nie będzie. W końcu ciężarówka nie dba o to, ile ją załadujesz - nadal będzie jechała z mniej więcej tą samą prędkością i dotrze na czas. Niezależnie od tego, czy mamy 800 terabajtów, czy 10 razy więcej danych, ciężarówka i tak dotrze tam w 5 dni. Innymi słowy, algorytm dostarczania danych ciężarówką ma stałą złożoność . „Stała” oznacza, że nie jest ona zależna od danych przekazywanych do algorytmu. Włóż do ciężarówki pendrive o pojemności 1 GB, a przyjedzie w ciągu 5 dni. Umieść tam dyski z 800 terabajtami danych, a przyjdą za 5 dni. Podczas korzystania z Big-O stałą złożoność oznacza się jako O(1) . Odkąd poznaliśmy O(N) iO(1) , spójrzmy teraz na więcej przykładów „programistycznych” :) Załóżmy, że masz tablicę 100 liczb i zadaniem jest wydrukowanie każdej z nich na konsoli. Piszesz zwykłą pętlę 
W górnym wierszu obrazu widzimy posortowaną tablicę. Musimy w nim znaleźć liczbę 23. Zamiast iterować po liczbach, po prostu dzielimy tablicę na 2 części i sprawdzamy średnią liczbę w tablicy. Znajdujemy liczbę znajdującą się w komórce 4 i sprawdzamy ją (drugi rząd na obrazku). Ta liczba to 16, a my szukamy 23. Obecna liczba jest mniejsza. Co to znaczy? Że nie trzeba sprawdzać wszystkich poprzednich liczb (które znajdują się aż do liczby 16) : na pewno będą mniejsze od tej, której szukamy, ponieważ nasza tablica jest posortowana! Kontynuujmy poszukiwania wśród pozostałych 5 elementów. Zwróć uwagę:Przeprowadziliśmy tylko jedno sprawdzenie, ale wyeliminowaliśmy już połowę możliwych opcji. Zostało nam już tylko 5 elementów. Powtórzymy nasz krok - ponownie podziel pozostałą tablicę przez 2 i ponownie weź środkowy element (linia 3 na rysunku). Ta liczba wynosi 56 i jest większa niż ta, której szukamy. Co to znaczy? Że odrzucimy jeszcze 3 opcje - samą liczbę 56 i dwie liczby po niej (są zdecydowanie większe niż 23, ponieważ tablica jest posortowana). Do sprawdzenia pozostały nam już tylko 2 liczby (ostatni wiersz na rysunku) - liczby z indeksami tablicy 5 i 6. Sprawdzamy pierwszą z nich i właśnie tego szukaliśmy - liczby 23! Jego indeks = 5! Przyjrzyjmy się wynikom naszego algorytmu, a wtedy zrozumiemy jego złożoność. (Nawiasem mówiąc, teraz rozumiesz, dlaczego nazywa się to binarnym: jego istotą jest ciągłe dzielenie danych przez 2). Wynik jest imponujący! Gdybyśmy szukali żądanej liczby za pomocą wyszukiwania liniowego, potrzebowalibyśmy 10 kontroli, ale przy wyszukiwaniu binarnym zrobiliśmy to w 3! W najgorszym przypadku byłoby ich 4, gdyby na ostatnim etapie potrzebna nam liczba okazała się drugą, a nie pierwszą. A co z jego złożonością? To bardzo interesująca kwestia :) Algorytm wyszukiwania binarnego zależy w znacznie mniejszym stopniu od liczby elementów w tablicy niż algorytm wyszukiwania liniowego (czyli prostego wyliczenia). Przy 10 elementach w tablicy wyszukiwanie liniowe będzie wymagało maksymalnie 10 kontroli, a wyszukiwanie binarne będzie wymagało maksymalnie 4 kontroli. Różnica jest 2,5 razy. Ale w przypadku tablicy zawierającej 1000 elementów wyszukiwanie liniowe będzie wymagało 1000 kontroli, a wyszukiwanie binarne będzie wymagało tylko 10 ! Różnica jest już 100-krotna! Zwróć uwagę:liczba elementów tablicy wzrosła 100-krotnie (z 10 do 1000), a liczba niezbędnych sprawdzeń dla 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 sprawdza wyszukiwanie liniowe i łącznie 14 sprawdza w przypadku wyszukiwania binarnego. I znowu: liczba elementów wzrosła 1000 razy (z 10 do 10 000), ale liczba kontroli wzrosła tylko 3,5 razy (z 4 do 14). Złożoność algorytmu wyszukiwania binarnego jest logarytmiczna lub w notacji Big-O O(log n) . Dlaczego tak się nazywa? Logarytm jest odwrotnością potęgowania. Logarytm binarny służy do obliczania potęgi liczby 2. Na przykład mamy 10 000 elementów, które musimy sprawdzić za pomocą wyszukiwania binarnego. 
Teraz masz obraz przed oczami i wiesz, że wymaga to maksymalnie 14 kontroli. Ale co, jeśli nie masz obrazu przed oczami i musisz policzyć dokładną liczbę niezbędnych kontroli? Wystarczy odpowiedzieć na proste pytanie: do jakiej potęgi należy podnieść liczbę 2, aby otrzymany wynik był >= liczba sprawdzanych elementów? Dla 10000 będzie to potęga 14. 2 do potęgi 13 to za mało (8192) Ale 2 do potęgi 14 = 16384 to liczba spełniająca nasz warunek (jest to >= liczba elementów w tablicy). Znaleźliśmy logarytm - 14. Tyle kontroli potrzebujemy! :) Algorytmy i ich złożoność to temat zbyt obszerny, aby ująć go w jednym wykładzie. Ale wiedza o tym jest bardzo ważna: w wielu rozmowach kwalifikacyjnych pojawią się problemy algorytmiczne. Dla teorii mogę polecić Ci kilka książek. Dobrym miejscem na rozpoczęcie jest „ Algorytmy grockingu ”: chociaż przykłady w tej książce są napisane w języku Python, język książki i przykłady są bardzo proste. Najlepsza opcja dla początkującego, a także ma niewielką objętość. Poważniejsza lektura: książki Roberta Laforeta i Roberta Sedgwicka . Obydwa są napisane w Javie, co ułatwi Ci naukę. W końcu doskonale znasz ten język! :) Dla studentów z dobrym przygotowaniem matematycznym najlepszą opcją będzie książka Thomasa Cormana . Ale nie zadowoli Cię tylko teoria! „Wiedzieć” != „być w stanie” Możesz poćwiczyć rozwiązywanie problemów algorytmicznych w HackerRank i Leetcode . Zadania stamtąd są często wykorzystywane nawet podczas rozmów kwalifikacyjnych w Google i Facebooku, więc na pewno nie będziesz się nudzić :) Dla utrwalenia materiału z wykładu radzę obejrzeć świetny film o Big-O na YouTube. Do zobaczenia na kolejnych wykładach! :)
GO TO FULL VERSION