Řád složitosti je termín používaný v informatice k měření účinnosti algoritmu nebo programu. Vztahuje se k množství času a zdrojů potřebných k vyřešení problému nebo provedení úkolu. V programování je řád složitosti obvykle vyjádřen v termínech Velký O notace, která udává horní hranici časových nebo prostorových požadavků algoritmu. V tomto článku se budeme zabývat řádem složitosti v programovacím jazyce C a jeho významem.
Pořadí složitosti v programovacím jazyce C:
V programování v jazyce C závisí pořadí složitosti algoritmu na počtu operací prováděných programem. Máme-li například pole o velikosti n a chceme v poli vyhledat konkrétní prvek, bude pořadí složitosti algoritmu záviset na počtu prvků v poli. Pokud provedeme a Lineární vyhledávání přes pole bude řád složitosti Na) , což znamená, že čas potřebný k vyhledání prvku se lineárně zvýší s velikostí pole. Pokud použijeme a Binární vyhledávací algoritmus místo toho bude řád složitosti O(log n) , což znamená, že čas potřebný k vyhledání prvku se bude logaritmicky prodlužovat s velikostí pole.
Podobně je tomu u Řádu složitosti dalších algoritmů, jako např Algoritmy řazení , Grafové algoritmy , a Algoritmy dynamického programování závisí také na počtu operací, které program provede. Pořadí složitosti těchto algoritmů lze vyjádřit pomocí Velký O notový zápis.
Podívejme se na některé běžné řády složitosti a jejich odpovídající algoritmy:
To znamená, že algoritmu trvá konstantní množství času bez ohledu na velikost vstupu. Například přístup k prvku v poli trvá O(1) čas, protože k prvku lze přistupovat přímo pomocí jeho indexu.
To znamená, že čas potřebný pro algoritmus roste logaritmicky s velikostí vstupu. To je běžně vidět v Algoritmy rozděl a panuj jako Binární vyhledávání , které rozdělují vstup na menší části pro vyřešení problému.
konverze řetězce java na celé číslo
To znamená, že čas strávený algoritmem roste lineárně s velikostí vstupu. Příklady takových algoritmů jsou Lineární vyhledávání a Bublinové řazení .
To znamená, že čas strávený algoritmem se zvýší o n vynásobený logaritmem n. Příklady takových algoritmů jsou Rychlé řazení a Sloučit třídění .
To znamená, že čas potřebný pro algoritmus se zvyšuje kvadraticky s velikostí vstupu. Příklady takových algoritmů jsou Bublinové řazení a Řazení vkládání .
To znamená, že čas potřebný pro algoritmus se zdvojnásobí s každým zvýšením velikosti vstupu. To je běžně vidět v Rekurzivní algoritmy jako Řada Fibonacci .
str.replace v jazyce Java
Je důležité vědět, že řád složitosti poskytuje pouze horní hranici času, který algoritmus potřebuje. Skutečný čas může být mnohem kratší než tato hranice, v závislosti na vstupních datech a implementaci algoritmu.
Při programování v jazyce C může být řád složitosti algoritmu určen analýzou kódu a počítáním počtu provedených operací. Například, pokud máme smyčku, která iteruje polem velikosti n, bude časová složitost smyčky Na) . Podobně, pokud máme rekurzivní funkci, která se volá kkrát, bude časová složitost funkce O(2^k) .
Pro optimalizaci výkonu programu je důležité zvolit algoritmy s nižším řádem složitosti. Pokud například potřebujeme seřadit pole, měli bychom použít třídicí algoritmus s nižším řádem složitosti, jako je např. Rychlé řazení nebo Sloučit třídění , spíše než Bublinové řazení , který má vyšší řád složitosti.
Analýza pořadí složitosti:
Abychom mohli analyzovat pořadí složitosti algoritmu, musíme určit, jak roste jeho doba běhu nebo využití prostoru s rostoucí velikostí vstupu. Nejběžnější metodou, jak toho dosáhnout, je spočítat počet základních operací provedených algoritmem.
Základní operace je operace, jejíž provedení trvá konstantní množství času, jako je přidání dvou čísel nebo přístup k prvku pole. Počítáním počtu základních operací provedených algoritmem v závislosti na velikosti vstupu můžeme určit jeho pořadí složitosti.
Zvažte například následující funkci C, která vypočítá součet prvních n celých čísel:
C kód:
int sum(int n) { int total = 0; for (int i = 1; i <= n; i++) { total +="i;" } return total; < pre> <p>In this function, the loop runs n times, and each iteration performs a constant amount of work (adding i to the total). Therefore, the number of basic operations performed by this algorithm is proportional to n, and its time complexity is <strong>O(n)</strong> .</p> <hr></=>