Ściągawka Big O: objaśniona na przykładach w języku Python

Analiza Big O to technika analizy i rankingu wydajności algorytmów.

Dzięki temu można wybrać najbardziej wydajne i skalowalne algorytmy. Ten artykuł jest ściągawką Big O wyjaśniającą wszystko, co musisz wiedzieć o notacji Big O.

Co to jest analiza Big O?

Analiza Big O to technika pozwalająca analizować skuteczność skalowania algorytmów. W szczególności pytamy, jak skuteczny jest algorytm w miarę wzrostu rozmiaru danych wejściowych.

Wydajność to stopień wykorzystania zasobów systemowych podczas tworzenia danych wyjściowych. Zasoby, którymi się zajmujemy to przede wszystkim czas i pamięć.

Dlatego też, wykonując analizę Big O, zadajemy następujące pytania:

Jak zmienia się wykorzystanie pamięci przez algorytm wraz ze wzrostem rozmiaru danych wejściowych?

Jaki jest czas potrzebny algorytmowi na wygenerowanie zmiany wyniku w miarę wzrostu rozmiaru danych wejściowych?

Odpowiedzią na pierwsze pytanie jest złożoność przestrzenna algorytmu, natomiast na drugie pytanie – jego złożoność czasowa. Do wyrażenia odpowiedzi na oba pytania używamy specjalnego zapisu zwanego notacją Big O. Zostanie to omówione w dalszej części Ściągawki Big O.

Warunki wstępne

Zanim przejdziemy dalej, muszę powiedzieć, że aby w pełni wykorzystać tę ściągawkę Big O, musisz zrozumieć trochę algebry. Ponadto, ponieważ będę podawać przykłady Pythona, przydatne będzie również zrozumienie trochę Pythona. Dogłębne zrozumienie nie jest konieczne, ponieważ nie będziesz pisać żadnego kodu.

Jak przeprowadzić analizę Big O

W tej sekcji omówimy sposób przeprowadzenia analizy Big O.

Podczas wykonywania analizy złożoności Big O należy pamiętać, że wydajność algorytmu zależy od struktury danych wejściowych.

Na przykład algorytmy sortowania działają najszybciej, gdy dane na liście są już posortowane we właściwej kolejności. Jest to najlepszy scenariusz wydajności algorytmu. Z drugiej strony te same algorytmy sortowania działają najwolniej, gdy struktura danych jest odwrotna. To najgorszy scenariusz.

Wykonując analizę Big O, bierzemy pod uwagę tylko najgorszy scenariusz.

Analiza złożoności przestrzeni

Rozpocznijmy tę ściągawkę Big O od omówienia sposobu przeprowadzania analizy złożoności przestrzeni. Chcemy rozważyć, w jaki sposób dodatkowa pamięć wykorzystywana przez algorytm skaluje się w miarę zwiększania się danych wejściowych.

Na przykład poniższa funkcja używa rekurencji do pętli od n do zera. Ma złożoność przestrzenną, która jest wprost proporcjonalna do n. Dzieje się tak, ponieważ wraz ze wzrostem n rośnie liczba wywołań funkcji na stosie wywołań. Zatem ma złożoność przestrzenną O(n).

def loop_recursively(n):
    if n == -1:
        return
    else:
        print(n)
        loop_recursively(n - 1)

Jednak lepsza implementacja wyglądałaby tak:

def loop_normally(n):
    count = n
    while count >= 0:
        print(count)
        count =- 1

W powyższym algorytmie tworzymy tylko jedną dodatkową zmienną i używamy jej do zapętlenia. Gdyby n rosło coraz bardziej, nadal używalibyśmy tylko jednej dodatkowej zmiennej. Dlatego algorytm ma stałą złożoność przestrzenną, oznaczoną symbolem „O(1)”.

Porównując złożoność przestrzenną dwóch powyższych algorytmów, doszliśmy do wniosku, że pętla while jest bardziej wydajna niż rekurencja. To jest główny cel Big O Analysis: analiza, jak zmieniają się algorytmy, gdy uruchamiamy je z większymi danymi wejściowymi.

Analiza złożoności czasu

Wykonując analizę złożoności czasowej, nie przejmujemy się wzrostem całkowitego czasu działania algorytmu. Niepokoi nas raczej wzrost liczby podejmowanych kroków obliczeniowych. Dzieje się tak dlatego, że faktyczny czas zależy od wielu czynników systemowych i losowych, które trudno uwzględnić. Zatem śledzimy jedynie wzrost kroków obliczeniowych i zakładamy, że każdy krok jest równy.

Aby pomóc w zademonstrowaniu analizy złożoności czasowej, rozważ następujący przykład:

Załóżmy, że mamy listę użytkowników, na której każdy użytkownik ma identyfikator i nazwę. Naszym zadaniem jest zaimplementowanie funkcji zwracającej nazwę użytkownika po nadaniu mu identyfikatora. Oto jak możemy to zrobić:

users = [
    {'id': 0, 'name': 'Alice'},
    {'id': 1, 'name': 'Bob'},
    {'id': 2, 'name': 'Charlie'},
]

def get_username(id, users):
    for user in users:
        if user['id'] == id:
            return user['name']
    return 'User not found'

get_username(1, users)

Mając listę użytkowników, nasz algorytm przegląda całą tablicę użytkowników, aby znaleźć użytkownika o prawidłowym identyfikatorze. Gdy mamy 3 użytkowników, algorytm wykonuje 3 iteracje. Kiedy mamy 10, wykonuje 10.

Dlatego liczba kroków jest liniowo i wprost proporcjonalna do liczby użytkowników. Zatem nasz algorytm ma liniową złożoność czasową. Możemy jednak ulepszyć nasz algorytm.

Załóżmy, że zamiast przechowywać użytkowników na liście, zapisaliśmy ich w słowniku. Wtedy nasz algorytm wyszukiwania użytkownika wyglądałby następująco:

users = {
    '0': 'Alice',
    '1': 'Bob',
    '2': 'Charlie'
}

def get_username(id, users):
     if id in users:
         return users[id]
     else:
         return 'User not found'

get_username(1, users)

Załóżmy, że w przypadku tego nowego algorytmu mamy 3 użytkowników w naszym słowniku; wykonalibyśmy kilka kroków, aby uzyskać nazwę użytkownika. Załóżmy, że mamy więcej użytkowników, powiedzmy dziesięciu. Aby pozyskać użytkownika, wykonalibyśmy tę samą liczbę kroków co poprzednio. Wraz ze wzrostem liczby użytkowników liczba kroków potrzebnych do uzyskania nazwy użytkownika pozostaje stała.

Dlatego ten nowy algorytm ma stałą złożoność. Nie ma znaczenia ilu mamy użytkowników; liczba wykonanych kroków obliczeniowych jest taka sama.

Co to jest notacja dużego O?

W poprzedniej sekcji omówiliśmy, jak obliczyć złożoność przestrzenną i czasową Wielkiego O dla różnych algorytmów. Do opisu złożoności używaliśmy słów takich jak liniowy i stały. Innym sposobem opisania złożoności jest użycie notacji dużego O.

Notacja dużego O to sposób na przedstawienie złożoności przestrzennej lub czasowej algorytmu. Notacja jest stosunkowo prosta; jest to litera O, po której następują nawiasy. Wewnątrz nawiasów piszemy funkcję n, która reprezentuje określoną złożoność.

Złożoność liniową reprezentuje n, więc zapisalibyśmy ją jako O(n) (czytaj jako „O z n”). Stała złożoność jest reprezentowana przez 1, więc zapisalibyśmy ją jako O(1).

Jest więcej zawiłości, które omówimy w następnej sekcji. Ale ogólnie, aby napisać złożoność algorytmu, wykonaj następujące kroki:

Spróbuj opracować funkcję matematyczną n, f(n), gdzie f(n) to ilość wykorzystanej przestrzeni lub kroki obliczeniowe, po których następuje algorytm, a n to rozmiar danych wejściowych.

Weź najbardziej dominujący wyraz w tej funkcji. Kolejność dominacji różnych terminów od najbardziej dominującego do najmniej dominującego jest następująca: silnia, wykładnicza, wielomianowa, kwadratowa, liniowa, liniowa, logarytmiczna i stała.

Usuń wszystkie współczynniki z wyrazu.

Wynikiem tego staje się termin, którego używamy w nawiasach.

Przykład:

Rozważ następującą funkcję Pythona:

users = [
    'Alice',
    'Bob',
    'Charlie'
]

def print_users(users):
    number_of_users = len(users)
    print("Total number of users:", number_of_users)

    for i in number_of_users:
        print(i, end=': ')
        print(user)

Teraz obliczymy złożoność algorytmu w czasie Big O.

Najpierw piszemy funkcję matematyczną nf(n), która reprezentuje liczbę kroków obliczeniowych wykonywanych przez algorytm. Przypomnijmy, że n reprezentuje rozmiar wejściowy.

Z naszego kodu funkcja wykonuje dwa kroki: jeden w celu obliczenia liczby użytkowników, a drugi w celu wydrukowania liczby użytkowników. Następnie dla każdego użytkownika wykonuje dwa kroki: jeden w celu wydrukowania indeksu, drugi w celu wydrukowania użytkownika.

Dlatego funkcję, która najlepiej reprezentuje liczbę wykonanych kroków obliczeniowych, można zapisać jako f(n) = 2 + 2n. Gdzie n to liczba użytkowników.

Przechodząc do kroku drugiego, wybieramy najbardziej dominujący termin. 2n jest wyrazem liniowym, a 2 jest wyrazem stałym. Liniowość jest bardziej dominująca niż stała, więc wybieramy 2n, składnik liniowy.

Zatem nasza funkcja ma teraz postać f(n) = 2n.

Ostatnim krokiem jest wyeliminowanie współczynników. W naszej funkcji mamy współczynnik 2. Więc to eliminujemy. I funkcja staje się f(n) = n. To jest termin, którego używamy w nawiasach.

Dlatego złożoność czasowa naszego algorytmu wynosi O(n) lub złożoność liniowa.

Różne złożoności Big O

Ostatnia sekcja naszej ściągawki Big O pokaże Ci różne złożoności i powiązane z nimi wykresy.

#1. Stały

Stała złożoność oznacza, że ​​algorytm wykorzystuje stałą ilość przestrzeni (przy analizie złożoności przestrzennej) lub stałą liczbę kroków (przy analizie złożoności czasowej). Jest to najbardziej optymalna złożoność, ponieważ algorytm nie potrzebuje dodatkowej przestrzeni ani czasu w miarę wzrostu danych wejściowych. Jest zatem bardzo skalowalny.

Stała złożoność jest reprezentowana jako O (1). Jednak nie zawsze jest możliwe napisanie algorytmów działających ze stałą złożonością.

#2. Logarytmiczny

Złożoność logarytmiczna jest reprezentowana przez termin O (log n). Należy zauważyć, że jeśli podstawa logarytmu nie jest określona w informatyce, zakładamy, że wynosi ona 2.

Dlatego log n to log2n. Wiadomo, że funkcje logarytmiczne początkowo rosną szybko, a następnie zwalniają. Oznacza to, że skalują się i działają efektywnie z coraz większą liczbą n.

#3. Liniowy

W przypadku funkcji liniowych, jeśli zmienna niezależna skaluje się o współczynnik p. Zmienna zależna skaluje się o ten sam współczynnik p.

Dlatego funkcja o złożoności liniowej rośnie o ten sam współczynnik, co rozmiar wejściowy. Jeśli rozmiar danych wejściowych podwoi się, zwiększy się także liczba kroków obliczeniowych i zużycie pamięci. Złożoność liniowa jest reprezentowana przez symbol O(n).

#4. Liniowy

O (n * log n) reprezentuje funkcje liniowe. Funkcje liniowe to funkcja liniowa pomnożona przez funkcję logarytmiczną. Dlatego funkcja liniowa daje wyniki nieco większe niż funkcje liniowe, gdy log n jest większe niż 1. Dzieje się tak, ponieważ n wzrasta po pomnożeniu przez liczbę większą niż 1.

Log n jest większy niż 1 dla wszystkich wartości n większych niż 2 (pamiętaj, log n to log2n). Dlatego dla dowolnej wartości n większej niż 2 funkcje liniowe są mniej skalowalne niż funkcje liniowe. Z czego n jest w większości przypadków większe niż 2. Zatem funkcje liniowe są generalnie mniej skalowalne niż funkcje logarytmiczne.

#5. Kwadratowy

Złożoność kwadratowa jest reprezentowana przez O(n2). Oznacza to, że jeśli rozmiar danych wejściowych zwiększy się 10 razy, liczba wykonanych kroków lub wykorzystana przestrzeń wzrośnie 102 razy lub 100! Nie jest to zbyt skalowalne i jak widać na wykresie, złożoność rośnie bardzo szybko.

Złożoność kwadratowa pojawia się w algorytmach, w których wykonuje się n razy pętlę, a dla każdej iteracji wykonuje się ją ponownie n razy, na przykład w przypadku sortowania bąbelkowego. Chociaż generalnie nie jest to idealne rozwiązanie, czasami nie ma innego wyjścia, jak tylko wdrożyć algorytmy o złożoności kwadratowej.

#6. Wielomian

Algorytm o złożoności wielomianowej jest reprezentowany przez O(np), gdzie p jest pewną stałą liczbą całkowitą. P reprezentuje kolejność, w jakiej n jest podnoszone.

Ta złożoność pojawia się, gdy masz liczbę zagnieżdżonych pętli. Różnica między złożonością wielomianową a złożonością kwadratową jest kwadratowa i jest rzędu 2, podczas gdy wielomian ma dowolną liczbę większą niż 2.

#7. Wykładniczy

Złożoność wykładnicza rośnie jeszcze szybciej niż złożoność wielomianowa. W matematyce domyślną wartością funkcji wykładniczej jest stała e (liczba Eulera). Jednak w informatyce domyślną wartością funkcji wykładniczej jest 2.

Złożoność wykładniczą reprezentuje symbol O(2n). Gdy n wynosi 0, 2n wynosi 1. Ale gdy n wzrasta do 5, 2n zwiększa się do 32. Wzrost n o jeden podwoi poprzednią liczbę. Dlatego funkcje wykładnicze nie są bardzo skalowalne.

#8. Silnia

Złożoność silniowa jest reprezentowana przez symbol O(n!). Ta funkcja również rośnie bardzo szybko i dlatego nie jest skalowalna.

Wniosek

W tym artykule omówiono analizę Big O i sposób jej obliczenia. Omówiliśmy także różne złożoności i omówiliśmy ich skalowalność.

Następnie możesz poćwiczyć analizę Big O na algorytmie sortowania w Pythonie.