Notacja Big O - po prostu wyjaśniona za pomocą ilustracji i wideo

Notacja Big O jest używana do komunikowania szybkości algorytmu. Może to być ważne przy ocenie algorytmów innych osób oraz przy ocenie własnych! W tym artykule wyjaśnię, czym jest notacja Big O i podam listę najczęstszych czasów działania algorytmów, które jej używają.

Czas działania algorytmu rośnie w różnym tempie

Mój syn Judasz ma dużo zabawek. W rzeczywistości zdobył miliard zabawek! Zdziwiłbyś się, jak szybko dziecko może zdobyć tyle zabawek, jeśli jest pierwszym wnukiem z obu stron rodziny. ??

W każdym razie Judasz ma problem. Kiedy jego przyjaciele odwiedzają go i chcą pobawić się określoną zabawką, znalezienie zabawki może zająć ZAWSZE. Chce więc stworzyć algorytm wyszukiwania, który pomoże mu znaleźć konkretną zabawkę tak szybko, jak to możliwe. Próbuje wybrać pomiędzy dwoma różnymi algorytmami wyszukiwania: wyszukiwaniem prostym i wyszukiwaniem binarnym. (Nie martw się, jeśli nie znasz tych algorytmów).

Wybrany algorytm musi być szybki i poprawny. Z jednej strony wyszukiwanie binarne jest szybsze. Judasz często ma tylko około 30 sekund, zanim jego przyjaciel znudzi się szukaniem zabawki. Z drugiej strony prosty algorytm wyszukiwania jest łatwiejszy do napisania i istnieje mniejsza szansa na wprowadzenie błędów. Z pewnością byłoby żenujące, gdyby jego przyjaciel znalazł błędy w swoim kodzie! Aby zachować szczególną ostrożność, Judah decyduje się na czas dla obu algorytmów za pomocą listy 100 zabawek.

Załóżmy, że sprawdzenie jednej zabawki zajmuje 1 milisekundę. W przypadku prostego wyszukiwania Judah musi sprawdzić 100 zabawek, więc wyszukiwanie trwa 100 ms. Z drugiej strony musi sprawdzić tylko 7 zabawek za pomocą wyszukiwania binarnego (log2 100 to mniej więcej 7, nie martw się, jeśli ta matematyka jest myląca, ponieważ nie jest to główny punkt tego artykułu), więc wyszukiwanie trwa 7 ms biegać. Ale tak naprawdę na liście będzie miliard zabawek. Jeśli tak, jak długo potrwa proste wyszukiwanie? Jak długo potrwa wyszukiwanie binarne?

Czas działania dla wyszukiwania prostego w porównaniu z wyszukiwaniem binarnym, z listą 100 elementów

Judah przeprowadza wyszukiwanie binarne z 1 miliardem zabawek i zajmuje to 30 ms (log2 1000000000 to mniej więcej 30). „32 ms!” on myśli. „Wyszukiwanie binarne jest około 15 razy szybsze niż wyszukiwanie proste, ponieważ wyszukiwanie proste trwało 100 ms przy 100 elementach, a wyszukiwanie binarne 7 ms. Więc proste wyszukiwanie zajmie 30 × 15 = 450 ms, prawda? Mój przyjaciel nudzi się o wiele poniżej 30 sekund ”. Judasz decyduje się na proste wyszukiwanie. Czy to właściwy wybór?

Nie. Okazuje się, że Judasz się mylił i stracił przyjaciela na całe życie. ? Czas wykonywania prostego wyszukiwania z 1 miliardem pozycji wyniesie 1 miliard ms, czyli 11 dni! Problem polega na tym, że czasy wykonywania wyszukiwania binarnego i wyszukiwania prostego nie rosną w tym samym tempie.

Czas pracy rośnie z bardzo różnymi prędkościami! Wraz ze wzrostem liczby elementów wyszukiwanie binarne zajmuje trochę więcej czasu, ale proste wyszukiwanie zajmuje znacznie więcej czasu. Ponieważ lista liczb się powiększa, wyszukiwanie binarne staje się nagle znacznie szybsze niż proste wyszukiwanie.

Więc Judah mylił się, twierdząc, że wyszukiwanie binarne jest zawsze 15 razy szybsze niż proste wyszukiwanie. Jeśli jest 1 miliard zabawek, jest to 33 miliony razy szybsze.

Bardzo ważne jest, aby wiedzieć, jak wydłuża się czas działania wraz ze wzrostem rozmiaru listy. Tutaj pojawia się notacja Big O.

Notacja Big O mówi ci, jak szybki jest algorytm. Na przykład załóżmy, że masz listę o rozmiarze n . Proste wyszukiwanie wymaga sprawdzenia każdego elementu, więc zajmie n operacji. Czas wykonania w notacji Big O to O ( n ).

Gdzie są sekundy? Nie ma - Big O nie podaje prędkości w kilka sekund. Notacja Big O pozwala porównać liczbę operacji. Informuje, jak szybko rozwija się algorytm.

Zróbmy inny przykład. Wyszukiwanie binarne wymaga operacji log n , aby sprawdzić listę o rozmiarze n . Jaki jest czas trwania w notacji Big O? To O (log n ). Ogólnie notacja Big O jest zapisana w następujący sposób.

To mówi, ile operacji wykona algorytm. Nazywa się to notacją duże O, ponieważ przed liczbą operacji umieszcza się „duże O”.

Big O ustala najgorszy czas działania

Załóżmy, że używasz prostego wyszukiwania, aby znaleźć użytkownika w bazie danych użytkowników. Wiesz, że wykonanie prostego wyszukiwania zajmuje O ( n ) czasu, co oznacza, że ​​w najgorszym przypadku algorytm będzie musiał przejrzeć każdego użytkownika w bazie danych. W tym przypadku szukasz użytkownika o nazwie „aardvark213”. To jest pierwszy użytkownik na liście. Twój algorytm nie musiał więc sprawdzać każdego wpisu - znalazł go za pierwszym razem. Czy algorytm zajął O ( n ) czasu? A może zajęło to O (1) czasu, ponieważ znalazło osobę za pierwszym razem?

Proste wyszukiwanie wciąż zajmuje O ( n ) czasu. W tym przypadku algorytm natychmiast znalazł to, czego szukał. To najlepszy scenariusz. Ale notacja Big O dotyczy najgorszego scenariusza. Można więc powiedzieć, że w najgorszym przypadku algorytm będzie musiał raz przejrzeć każdego użytkownika w bazie danych. To jest O ( n ) czas. To zapewnienie - wiesz, że proste wyszukiwanie nigdy nie będzie wolniejsze niż czas O ( n ).

Niektóre typowe czasy działania Big O.

Oto pięć czasów działania Big O, z którymi często się spotykasz, posortowanych od najszybszych do najwolniejszych:

  • O (log n ), znany również jako czas logowania. Przykład: wyszukiwanie binarne.
  • O ( n ), znany również jako czas liniowy . Przykład: proste wyszukiwanie.
  • O ( n * log n ). Przykład: algorytm szybkiego sortowania, taki jak quicksort.
  • O ( nr 2). Przykład: powolny algorytm sortowania, taki jak sortowanie przez wybór.
  • O ( n !). Przykład: naprawdę powolny algorytm, na przykład podróżujący sprzedawca.

Wizualizacja różnych czasów działania Big O.

Załóżmy, że rysujesz siatkę 16 ramek i możesz wybrać jeden z 5 różnych algorytmów, aby to zrobić. Jeśli użyjesz pierwszego algorytmu, narysowanie siatki zajmie ci O (log n ) czasu. Możesz wykonać 10 operacji na sekundę. Mając czas O (log n ), narysowanie siatki składającej się z 16 pól zajmie ci 4 operacje (log 16 o podstawie 2 to 4). Więc narysowanie siatki zajmie ci 0,4 sekundy. A co, jeśli musisz narysować 1024 pudełka? Zajmie ci to zarejestrowanie 1024 = 10 operacji lub 1 sekundę, aby narysować siatkę 1024 pól. Te liczby używają pierwszego algorytmu.

Drugi algorytm jest wolniejszy: zajmuje O ( n ) czasu. Narysowanie 16 pudełek będzie wymagało 16 operacji, a narysowanie 1024 pudełek - 1024 operacji. Ile to czasu w sekundach?

Oto, ile czasu zajmie narysowanie siatki dla pozostałych algorytmów, od najszybszego do najwolniejszego:

Istnieją również inne czasy działania, ale to pięć najczęściej używanych.

To jest uproszczenie. W rzeczywistości nie można tak dokładnie przekonwertować czasu wykonywania Big O na wiele operacji, ale jest to dobre oszacowanie.

Wniosek

Oto główne wnioski:

  • Szybkość algorytmu nie jest mierzona w sekundach, ale we wzroście liczby operacji.
  • Zamiast tego mówimy o tym, jak szybko czas działania algorytmu rośnie wraz ze wzrostem rozmiaru danych wejściowych.
  • Czas działania algorytmów jest wyrażany w notacji Big O.
  • O (log n ) jest szybsze niż O ( n ), ale staje się dużo szybsze, gdy rośnie lista elementów, których szukasz.

A oto film, który obejmuje wiele z tego, co jest w tym artykule, i nie tylko.

Mam nadzieję, że ten artykuł przybliżył ci więcej o notacji Big O Ten artykuł jest oparty na lekcji z mojego kursu wideo z Manning Publications pt. Algorithms in Motion. Kurs oparty jest na niesamowitej książce Grokking Algorithms autorstwa Sztolni Bhargava. To on narysował wszystkie zabawne ilustracje w tym artykule.

Jeśli najlepiej uczysz się z książek, zdobądź książkę! Jeśli najlepiej uczysz się poprzez filmy, rozważ zakup mojego kursu. Możesz uzyskać 39% zniżki na mój kurs, używając kodu „ 39carnes ”.