Co to jest notacja Big-O?

Czy kiedykolwiek zastanawiałeś się, dlaczego napisany przez Ciebie program tak długo się uruchamia? Być może chciałbyś wiedzieć, czy możesz zwiększyć wydajność swojego kodu. Zrozumienie, jak działa kod, może przenieść go na wyższy poziom. Notacja Big-O to przydatne narzędzie do obliczania, jak wydajny jest Twój kod.

Co to jest notacja Big-O?

Notacja Big-O umożliwia obliczenie, ile czasu zajmie wykonanie kodu. Możesz fizycznie określić, ile czasu zajmie wykonanie kodu, ale dzięki tej metodzie trudno jest wychwycić niewielkie różnice czasowe. Na przykład czas między uruchomieniem 20 a 50 linii kodu jest bardzo mały. Jednak w dużym programie te nieefektywności mogą się sumować.

Notacja Big-O liczy, ile kroków algorytm musi wykonać, aby ocenić swoją efektywność. Podejście do kodu w ten sposób może być bardzo skuteczne, jeśli musisz dostroić kod w celu zwiększenia wydajności. Notacja Big-O umożliwi pomiar różnych algorytmów na podstawie liczby kroków wymaganych do wykonania i obiektywne porównanie wydajności algorytmów.

Jak obliczyć notację Big-O

Rozważmy dwie funkcje, które liczą, ile pojedynczych skarpet znajduje się w szufladzie. Każda funkcja przyjmuje liczbę par skarpet i zwraca liczbę pojedynczych skarpet. Kod jest napisany w Pythonie, ale nie ma to wpływu na to, jak policzylibyśmy liczbę kroków.

Algorytm 1:

def sockCounter (numberOfPairs):
IndividualSocks = 0
dla x w zakresie (numberOfPairs):
IndividualSocks = indywidualnySocks + 2
powrót indywidualnySocks

Algorytm 2:

def sockCounter (numberOfPairs):
return numberOfPairs * 2

To głupi przykład i powinieneś być w stanie łatwo stwierdzić, który algorytm jest bardziej wydajny. Ale dla praktyki przejrzyjmy każdy z nich.

ZWIĄZANE Z: Co to jest funkcja w programowaniu?

Co to jest funkcja w programowaniu?

Jeśli uczysz się programowania własnego kodu, musisz zrozumieć, czym są funkcje.

Algorytm 1 ma wiele kroków:

1. Przypisuje wartość zero do zmiennej IndividualSocks.
2. Przypisuje wartość jeden zmiennej i.
3. Porównuje wartość i do numberOfPairs.
4. Dodaje dwa do pojedynczych skarpet.
5. Przypisuje sobie zwiększoną wartość poszczególnych skarpet.
6. Zwiększa się o jeden.
7. Następnie wykonuje pętlę z powrotem przez kroki od 3 do 6 tyle samo razy, co (individualSocks - 1).

Liczbę kroków, które musimy wykonać dla algorytmu, można wyrazić jako:

4n + 2

Są cztery kroki, które musimy wykonać n razy. W tym przypadku n byłoby równe wartości numberOfPairs. Istnieją również 2 kroki, które są wykonywane raz.

Dla porównania algorytm 2 ma tylko jeden krok. Wartość numberOfPairs jest mnożona przez dwa. Wyrazilibyśmy to jako:

1

Jeśli nie było to jeszcze widoczne, teraz możemy łatwo zobaczyć, że algorytm 2 jest o wiele bardziej wydajny.

Analiza Big-O

Ogólnie rzecz biorąc, gdy interesuje Cię notacja Big-O algorytmu, bardziej interesuje Cię ogólna wydajność, a mniej szczegółowa analiza liczby kroków. Aby uprościć zapis, możemy po prostu podać wielkość wydajności.

W powyższych przykładach algorytm 2 zostałby wyrażony jako jeden:

O (1)

Ale algorytm 1 zostałby uproszczony jako:

Na)

Ta szybka migawka mówi nam, jak wydajność algorytmu jeden jest powiązana z wartością n. Im większa liczba, tym więcej kroków algorytm będzie musiał wykonać.

Kod liniowy

Ponieważ nie znamy wartości n, bardziej pomocne jest zastanowienie się, jak wartość n wpływa na ilość kodu, który musi zostać uruchomiony. W algorytmie 1 możemy powiedzieć, że zależność jest liniowa. Jeśli wykreślisz liczbę kroków vs. wartość n otrzymujesz linię prostą, która idzie w górę.

Kod kwadratowy

Nie wszystkie relacje są tak proste, jak przykład liniowy. Wyobraź sobie, że masz tablicę 2D i chciałbyś wyszukać wartość w tablicy. Możesz stworzyć taki algorytm:

def searchForValue (targetValue, arraySearched):
foundTarget = False
for x in arraySearched:
dla y in x:
if (y == targetValue):
foundTarget = True
return foundTarget

W tym przykładzie liczba kroków zależy od liczby tablic w arraySearched i liczby wartości w każdej tablicy. Zatem uproszczona liczba kroków wynosiłaby n * n lub n².

Ta zależność jest zależnością kwadratową, co oznacza, że ​​liczba kroków w naszym algorytmie rośnie wykładniczo wraz z n. W notacji Big-O zapisałbyś to jako:

O (n²)

ZWIĄZANE Z: Przydatne narzędzia do sprawdzania, czyszczenia i optymalizacji plików CSS

Kod logarytmiczny

Chociaż istnieje wiele innych relacji, ostatnią relacją, której przyjrzymy się, są relacje logarytmiczne. Aby odświeżyć pamięć, log liczby jest wartością wykładnika wymaganą do osiągnięcia liczby o danej podstawie. Na przykład:

log 2 (8) = 3

Logarytm równa się trzy, ponieważ gdyby nasza podstawa była równa 2, potrzebowalibyśmy wykładnika o wartości 3, aby uzyskać liczbę 8.

Zatem zależność funkcji logarytmicznej jest przeciwieństwem relacji wykładniczej. Wraz ze wzrostem n potrzeba mniej nowych kroków do uruchomienia algorytmu.

Na pierwszy rzut oka wydaje się to sprzeczne z intuicją. W jaki sposób kroki algorytmu mogą rosnąć wolniej niż n? Dobrym tego przykładem są wyszukiwania binarne. Rozważmy algorytm wyszukiwania liczby w tablicy unikatowych wartości.

• Zaczniemy od tablicy do przeszukania w kolejności od najmniejszej do największej.
• Następnie sprawdzimy wartość w środku tablicy.
• Jeśli twoja liczba jest wyższa, wykluczamy z naszego wyszukiwania niższe liczby, a jeśli była niższa, wykluczamy wyższe liczby.
• Teraz przyjrzymy się środkowej liczbie pozostałych liczb.
• Ponownie wykluczymy połowę liczb na podstawie tego, czy nasza wartość docelowa jest wyższa, czy niższa od wartości środkowej.
• Będziemy kontynuować ten proces, aż znajdziemy nasz cel lub stwierdzimy, że nie ma go na liście.

Jak widać, ponieważ wyszukiwanie binarne eliminuje połowę możliwych wartości przy każdym przebiegu, ponieważ n rośnie, wpływ na liczbę sprawdzeń tablicy jest niewielki. Aby wyrazić to w notacji Big-O, napisalibyśmy:

O (log (n))

Znaczenie notacji Big-O

Big-O nation daje ci szybki i łatwy sposób na poinformowanie, jak wydajny jest algorytm. Ułatwia to wybór między różnymi algorytmami. Może to być szczególnie przydatne, jeśli używasz algorytmu z biblioteki i niekoniecznie wiesz, jak wygląda kod.

Kiedy po raz pierwszy uczysz się kodować, zaczynasz od funkcji liniowych. Jak widać na powyższym wykresie, zaprowadzi Cię to bardzo daleko. Ale gdy stajesz się bardziej doświadczony i zaczynasz tworzyć bardziej złożony kod, wydajność zaczyna stawać się problemem. Zrozumienie, jak oszacować wydajność kodu, da ci narzędzia potrzebne do rozpoczęcia jego dostrajania pod kątem wydajności oraz rozważenia zalet i wad algorytmów.

10 najczęstszych błędów w programowaniu i kodowaniu

Błędy w kodowaniu mogą prowadzić do wielu problemów. Te wskazówki pomogą Ci uniknąć błędów programistycznych i nadać kodowi znaczenie.

O autorze