Algoritmy a jak analyzovat jejich složitost

Algoritmy se účastní téměř všech úkolů, které denně plníme. Mnoho z nich spouštíme „automaticky“, aniž bychom si uvědomovali „na co“ se používají nebo „jak“ je používáme. Ve vývoji softwaru to není tak odlišné. Co ale jsou algoritmy? A proč je důležité analyzovat jejich složitost?

Pojďme to zjistit! :)

Co je to algoritmus?

Sada kroků nezbytných k provedení úkolu.

Počítačové programy nejsou jedinými věcmi, které provádějí algoritmy, jsou také prováděny a implementovány námi lidmi.

Přemýšleli jste například o algoritmu, který provádí následující úkoly?

  • Vyčisti si zuby
  • Vykoupat se
  • kuchařka
  • Jděte do práce z domova

V naší každodenní činnosti provádíme řadu kroků k dokončení alespoň jednoho z výše uvedených úkolů. Jako příklad použijeme řízení úkolů z práce z domova. Kroky, které podniknu, jsou v podstatě následující:

  1. Nastupte do mého auta
  2. Jeďte do domu přítele a projeďte je
  3. Jeďte do kanceláře, kde pracuji
  4. Zaparkuj moje auto v garáži

Toto je sada kroků (algoritmus), které musím provést, abych dokončil tento úkol.

Nyní přemýšlejte o nezbytných souborech kroků, které podniknete k provedení stejného úkolu. Je pravděpodobné, že se trochu liší od mých. Naše algoritmy se mohou lišit, ale náš cíl je stejný.

Počítačové programy se příliš neliší: Existuje celá řada algoritmů, které lze použít k provádění řady úkolů. Často se netýkáme toho, čím jsou, jednoduše je používáme (včetně mě).

Jak by měl vypadat například algoritmus používaný Waze a Mapami Google, ten, který počítá nejlepší trasu mezi dvěma místy? A co algoritmus Netflixu, který navrhuje filmy a seriály na základě toho, co jste sledovali?

Osobně jsem ti to nemohl říct. Vím však, že jsou efektivní. A efektivita je standard, který používáme k analýze složitosti algoritmu.

Co je to složitost algoritmů?

V informatice se složitost algoritmu týká množství času a prostoru, které algoritmus potřebuje k provedení úkolu, podle velikosti jeho vstupu.

Obecně jsou algoritmy hodnoceny podle jejich spotřeby času i prostoru, ale v tomto příspěvku se budu zabývat pouze časovou složitostí.

Analýza složitosti času nám umožňuje určit, jak se bude algoritmus chovat při nárůstu jeho vstupních prvků. Můžeme mít představu o tom, kolik času bude trvat zpracování 10, 100 nebo 1000 prvků.

A proč je tato analýza důležitá?

  • Určit, který algoritmus je nejúčinnější;
  • Umět vyvinout účinnější algoritmy;
  • Aby bylo možné analyzovat, zda je knihovna algoritmu nebo dokonce jeho skutečný jazyk efektivní.

Abych to shrnul, efektivita je to pravé!

Časová složitost

Čas potřebný k ukončení činnosti.

Můžeme začít analyzovat čas pomocí metody Frekvence počet, která v podstatě počítá, kolikrát je strojová instrukce vykonána. Každému kroku (instrukci) je přiřazena časová jednotka, počínaje 1.

Čas, který algoritmus spotřebuje, je vyjádřen funkcí f (n), kde n představuje velikost dat.

Výsledek analýzy je vyjádřen takto:

([funkce, která vyjadřuje čas]) = [Součet časových jednotek]

Nyní analyzujme některé algoritmy, abychom pochopili, jak to funguje ve skutečnosti.

První funkce sčítá dvě celá čísla:

Vidíme, že pro uvedený úkol implementovaný algoritmus provede pouze jeden krok: sčítání dvou čísel. Protože každému kroku přiřazujeme hodnotu, výsledkem je f (n) = 1.

Podívejme se na další příklad, což je algoritmus, který dělí celé číslo jiným celkovým číslem:

Přestože je matematická operace podobná sumaci, algoritmus obsahuje více kroků, protože je třeba zkontrolovat, zda je dělitel 0; pokud tomu tak je, rozdělení nebude realizováno. Protože máme celkem čtyři kroky a každému z nich je přiřazena hodnota 1, výsledkem je f (n) = 4.

Následující algoritmus shrnuje všechny prvky seznamu celých čísel:

V tomto algoritmu jeden z kroků obsahuje instrukce pro opakování; to znamená, že kód uvnitř pro bude proveden několikrát. Protože počet spuštění závisí na velikosti dat, hodnotu n přiřazujeme jako časovou jednotku. Výsledkem je f (n) = 2n + 3.

Následující algoritmus přidá součet jednoho seznamu se součtem druhého seznamu.

Výsledkem je f (n) = 2n² + 2n + 3.

Až do tohoto okamžiku jsme viděli pouze jednoduché algoritmy, že? Nyní si představte analýzu složitějších algoritmů a potřebu provést tyto výpočty? Není to proveditelné, že? Ačkoli se to jeví jako nejvhodnější, je to velmi pracné a na konci dne to nestojí za to.

Když analyzujeme algoritmus, obvykle se snažíme zjistit jeho chování, když existuje mnoho prvků, které je třeba zpracovat. Právě v těchto situacích musíme najít převládající termín součtu časových jednotek.

Jaký je například převládající termín součtu třetího algoritmu?

f (n) = 2n + 3

V tomto případě převládající termín ve 2 * n, a vysvětlím proč!

V jakékoli situaci, kdy n je větší než 1 (n> 1), bude mít produkt (výsledek násobení) hodnotu vyšší než druhý termín součtu.

Test něco: nahraďte n libovolným celkovým číslem větším než 1 a proveďte násobení.

A co převládající termín součtu posledního algoritmu?

f (n) = 2n² + 2n + 3

V tomto případě je dominantní termín 2 * n², protože když n> 1, bude produkt vždy větší než druhý a třetí člen součtu. Jděte do toho, vyzkoušejte to!

Ergo, existuje více obyčejný způsob, jak říci, analyzovat složitost algoritmů, kde jsou ignorovány konstanty a méně významné termíny. Tato metoda se nazývá asymptotická složitost.

Zde přichází do hry řád složitosti, známý také jako Notation-O nebo Big-O.

Big-O zápis

Používá se pro klasifikaci algoritmu s ohledem na rychlost růstu operací s rostoucím počtem zpracovaných prvků.

Big-O notace také definuje funkci, která vyjadřuje časovou složitost algoritmu. Za tímto účelem se n používá jako funkce písmene O.

Nejběžnější třídy jsou:

  • O (1) - Konstantní počet operací se nezvyšuje se zvyšujícím se počtem prvků
  • O (log n) - Logaritmický, počet operací je menší než počet prvků
  • O (n) - Lineární, počet operací roste úměrně s počtem prvků
  • O (n²) Kvadratický, počet operací bude větší než počet prvků
  • O (2 ^ n) - Exponencial, počet operací rychle roste ve srovnání s počtem prvků
  • O (n!) - Factorial, počet operací roste velmi, velmi rychle, dokonce pro malý počet elementů

Níže máme grafiku, která ilustruje míru růstu operací x množství prvků:

Grafika je klasifikována takto:

  • Červená zóna je hrozná, vyhýbejte se jí!
  • Oranžová zóna je špatná, vyhýbejte se jí také!
  • Žlutá zóna je spravedlivá, rozumná!
  • Světle zelená zóna je dobrá, v pohodě!
  • Tmavě zelená zóna je vynikající, gratulujeme!

Nyní použijeme notaci Big-O pro kategorizaci algoritmů, které byly dříve zmíněny, a vždy nás používají jako převládající výraz.

První algoritmus vyústil v f (n) = 1; což znamená, že nezávisle na nárůstu prvků provede algoritmus pouze jednu operaci. Algoritmus tedy můžeme klasifikovat jako Constant - O (1).

Druhý algoritmus vyústil v f (n) = 4; což znamená, že bez ohledu na nárůst prvků bude algoritmus provádět čtyři operace. Můžeme tedy také klasifikovat tento algoritmus jako Constant - O (1).

Výsledkem třetího algoritmu bylo f (n) = 2n + 3; což znamená, že počet operací poroste úměrně s počtem prvků, protože vidíme, jak n v této funkci slouží jako proměnná. Můžeme tedy tento algoritmus definovat jako lineární - O (n).

Výsledek posledního algoritmu vyústil v f (n) = 2n² + 2n + 3, což znamená, že počet operací vzroste více než počet prvků. V tomto případě n také slouží jako proměnná, ale je zvýšena na druhou mocninu (druhá mocnina). Můžeme tedy tento algoritmus definovat jako Kvadratický - O (n²).

Níže uvedená tabulka ilustruje nárůst počtu operací, protože se týká růstu počtu prvků.

Všimněte si, že v exponenciálním algoritmu by 16 prvků vedlo k nejméně 65 535 operacím. Docela znepokojující, že?

Obecně je proces analýzy stejný jako v předchozím případě: spočítání počtu kroků a určení převládajícího termínu.

Některé trendy můžeme pozorovat:

  • Algoritmy, které nemají opakovací smyčku, bývají konstantní - O (1)
  • Algoritmy, které mají opakující se smyčky, pokud nejsou vnořeny, mají tendenci být lineární - O (n)
  • Algoritmy, které mají dvě vnořené opakovací smyčky, bývají kvadratické - O (n²)
  • Přímý přístup k indexu pole je obvykle O (1) (konstanta)
  • Metody rozšíření seznamu jsou v průměru O (n). Například: libovolný, součet a filtr.
  • Algoritmy třídění, jako je třídění bublin, třídění vkládání a třídění výběru, jsou obvykle O (n²).

Vědět, jak klasifikovat algoritmy, nám dává schopnost posoudit účinnost nebo neefektivnost algoritmu. Přesný čas běhu nemůžeme samozřejmě měřit v sekundách, minutách nebo hodinách. Aby to bylo možné, musí být provedeno, změřeno a změněno. Představte si, že to děláte pro algoritmy, které zabírají hodiny nebo dokonce dny? Bez šance!

Doufám, že jsem splnil cíl tohoto příspěvku, kterým bylo poskytnout přehled algoritmů a jejich analýzu pomocí metod Frekvence počtu a Big-O.

Nechal jsem několik odkazů níže jako další materiál pro čtení!

Reference:

Vídeos 1 až 1.7

Chcete přinést inovaci na úvěrový trh pomocí technologie? Neustále hledáme nové lidi, kteří se připojí k naší posádce!

Podívejte se na naše otvory zde.