Velký O Cheat Sheet: Vysvětleno s příklady Pythonu

autor:
Tweet
Share
Share
Pin

Analýza Big O: Průvodce pro Hodnocení Algoritmů

Analýza Big O je klíčová technika pro zkoumání a hodnocení efektivity algoritmů. Umožňuje nám vybírat ty nejúčinnější a škálovatelné postupy. Tento článek slouží jako podrobný návod (Big O Cheat Sheet) k pochopení notace Big O.

Co je Analýza Big O?

Analýza Big O nám umožňuje posoudit, jak dobře se algoritmy škálují, zejména s ohledem na rostoucí objem vstupních dat. Zajímá nás, jak efektivně algoritmus využívá systémové zdroje – primárně čas a paměť – při generování výstupu.

Konkrétně se ptáme:

  • Jak se mění paměťové nároky algoritmu s rostoucím objemem dat?
  • Jak se mění čas potřebný pro výpočet výstupu s rostoucí velikostí vstupu?

Odpověď na první otázku je prostorová složitost, zatímco druhá se týká časové složitosti. K vyjádření těchto složitostí používáme notaci Big O, kterou si dále rozebereme.

Nezbytné Znalosti

Pro plné pochopení tohoto průvodce je výhodná základní znalost algebry a alespoň základní povědomí o programovacím jazyce Python, protože budeme uvádět příklady kódu. Hluboké znalosti programování však nejsou nutné.

Jak Provádět Analýzu Big O?

V této sekci se podíváme na to, jak analyzovat algoritmy pomocí Big O. Důležité je mít na paměti, že výkon algoritmu závisí na struktuře vstupních dat.

Například, algoritmy pro řazení pracují nejrychleji, pokud jsou data již seřazena – to je nejlepší scénář. Naopak, pokud jsou data seřazena v opačném pořadí, algoritmy běží nejpomaleji – to je nejhorší scénář. Při analýze Big O se zaměřujeme právě na nejhorší možný scénář.

Analýza Prostorové Složitosti

Začněme s analýzou prostorové složitosti. Zkoumáme, jak se mění paměťové nároky algoritmu s narůstajícím množstvím vstupních dat.

Například, následující rekurzivní funkce má prostorovou složitost přímo úměrnou ‚n‘, protože s rostoucím ‚n‘ roste i hloubka rekurze (počet volání funkce na zásobníku).

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

Tato funkce má prostorovou složitost O(n).

Alternativní implementace, která využívá cyklus while, má však konstantní prostorovou složitost. Bez ohledu na to, jak velké ‚n‘ je, funkce používá jen jednu pomocnou proměnnou.

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

Tato implementace má prostorovou složitost O(1). Porovnáním těchto dvou příkladů můžeme vidět, že cyklus while je efektivnější z hlediska využití paměti.

Analýza Časové Složitosti

Při analýze časové složitosti nás nezajímá absolutní čas běhu algoritmu, ale spíše počet provedených výpočetních kroků. Skutečný čas se totiž liší v závislosti na mnoha faktorech. Zaměřujeme se tedy pouze na růst počtu kroků s rostoucí velikostí vstupu, za předpokladu, že každý krok trvá stejně dlouho.

Uvažujme příklad s vyhledáváním uživatele podle ID v seznamu.

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)

Tento algoritmus má lineární časovou složitost. Počet kroků potřebných pro nalezení uživatele se lineárně zvyšuje s počtem uživatelů.

Pokud bychom však použili slovník (hash mapu) namísto seznamu, vyhledávání by probíhalo v konstantním čase. Bez ohledu na to, kolik uživatelů máme, počet kroků potřebných pro vyhledání uživatele zůstává stejný.

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)

V tomto případě má algoritmus konstantní časovou složitost.

Co je to Big O Notace?

Big O notace je způsob, jak formálně vyjádřit prostorovou nebo časovou složitost algoritmu. Používáme symbol O, následovaný závorkami, v nichž je uvedena funkce ‚n‘ reprezentující složitost. Například, lineární složitost se zapisuje jako O(n), zatímco konstantní složitost jako O(1).

Pro určení Big O složitosti algoritmu:

  1. Určíme matematickou funkci f(n), kde f(n) je počet kroků nebo paměť, kterou algoritmus používá, a n je velikost vstupu.
  2. Vybereme nejdominantnější člen této funkce (např. faktoriální > exponenciální > polynomiální > kvadratický > lineární > logaritmický > konstantní).
  3. Odstraníme koeficienty z tohoto dominantního členu.

Výsledný výraz v závorkách je Big O notace.

Příklad:

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)

Analýza časové složitosti:

Funkce provede jeden krok pro výpočet počtu uživatelů, jeden pro výpis tohoto čísla, a následně provede 2 kroky pro každého uživatele. Celkově tedy f(n) = 2 + 2n. Nejdominantnější člen je 2n, a po odstranění koeficientu získáme f(n) = n. Časová složitost tohoto algoritmu je tedy O(n).

Různé Big O Složitosti

Následující sekce představuje různé typy složitostí, které se v analýze Big O objevují.

#1. Konstantní

Konstantní složitost, O(1), znamená, že algoritmus spotřebovává konstantní množství paměti nebo provádí konstantní počet kroků bez ohledu na velikost vstupních dat. Je to nejoptimálnější složitost.

#2. Logaritmická

Logaritmická složitost, O(log n), se objevuje, když algoritmus dělí problém na menší části. Algoritmy s logaritmickou složitostí se škálují efektivně s rostoucím počtem vstupů.

#3. Lineární

Lineární složitost, O(n), znamená, že počet kroků nebo paměť roste lineárně s velikostí vstupu. Zdvojnásobení velikosti vstupu zdvojnásobí i počet kroků.

#4. Linearitmická

Linearitmická složitost, O(n log n), je kombinací lineární a logaritmické složitosti. Je typická pro efektivní algoritmy řazení. Růst počtu kroků je zde o něco větší než u lineární složitosti.

#5. Kvadratická

Kvadratická složitost, O(n2), znamená, že počet kroků roste kvadraticky s velikostí vstupu. Pokud se velikost vstupu zvětší 10krát, počet kroků se zvětší 100krát. Není příliš efektivní pro velké objemy dat.

#6. Polynomiální

Polynomiální složitost, O(np), kde ‚p‘ je konstanta, zahrnuje kvadratickou složitost. Růst složitosti je v tomto případě rychlejší než u kvadratické.

#7. Exponenciální

Exponenciální složitost, O(2n), je velmi neefektivní pro velké datové sady. Malé zvětšení vstupu způsobuje enormní nárůst počtu kroků.

#8. Faktoriální

Faktoriální složitost, O(n!), je nejméně škálovatelná a roste extrémně rychle. Používá se zřídka a pro malé vstupy.

Závěr

V tomto článku jsme probrali principy analýzy Big O, různé druhy složitostí a jejich důležitost při návrhu efektivních algoritmů. Prohloubíte si pochopení analýzy Big O tím, že si ji vyzkoušíte na různých třídicích algoritmech.