**Složitost algoritmu** je míra náročnosti algoritmu na výpočetní čas a paměť. Je důležitá pro pochopení, jak efektivní algoritmus je a jak se bude chovat pro různé velikosti vstupních dat. ### **Druhy složitosti** - **Časová složitost:** Udává, kolik času algoritmus potřebuje k provedení na daném vstupu. Obvykle se vyjadřuje jako funkce velikosti vstupu n. - **Paměťová složitost:** Udává, kolik paměti algoritmus potřebuje k provedení na daném vstupu. Obvykle se vyjadřuje jako funkce velikosti vstupu n. ### **Porovnání algoritmu z hlediska složitosti** Dva algoritmy se dají porovnat z hlediska složitosti, pokud řeší stejný problém. Algoritmus s menší časovou a paměťovou složitostí je považován za efektivnější. **Příklad:** - Bubblesort a quicksort jsou dva algoritmy pro řazení dat. Bubblesort má nejhorší časovou složitost O(n^2), zatímco quicksort má nejhorší časovou složitost O(n log n). To znamená, že quicksort bude pro velké datové soubory mnohem efektivnější než bubblesort. ### **Příklady složitostí algoritmů** - **Lineární složitost (O(n))**: Algoritmus s lineární složitostí se provádí v čase úměrném velikosti vstupu. Například vyhledávání prvku v seznamu. - **Kvadratická složitost (O(n^2))**: Algoritmus s kvadratickou složitostí se provádí v čase úměrném druhé mocnině velikosti vstupu. Například bubblesort. - **Logaritmická složitost (O(log n))**: Algoritmus s logaritmickou složitostí se provádí v čase úměrném logaritmu velikosti vstupu. Například binární vyhledávání. - **Exponenciální složitost (O(2^n))**: Algoritmus s exponenciální složitostí se provádí v čase úměrném exponenciální funkci velikosti vstupu. Takové algoritmy se obvykle v praxi nepoužívají, protože jsou velmi pomalé. **Tipy:** - Při výběru algoritmu je důležité zvážit jeho složitost a porovnat ji s požadavky na danou úlohu. - Existují online nástroje a knihovny, které vám pomohou s analýzou složitosti algoritmů. - Optimalizace algoritmů může vést k výraznému zlepšení jejich efektivity. Dobré pochopení složitosti algoritmů vám pomůže vybrat ten správný pro danou úlohu a optimalizovat váš program.