Poradie zložitosti je termín používaný v informatike na meranie účinnosti algoritmu alebo programu. Vzťahuje sa na množstvo času a zdrojov potrebných na vyriešenie problému alebo vykonanie úlohy. V programovaní sa Poradie zložitosti zvyčajne vyjadruje v termínoch Veľký O zápis, ktorý dáva hornú hranicu časových alebo priestorových požiadaviek algoritmu. V tomto článku budeme diskutovať o poradí zložitosti v programovacom jazyku C a jeho význame.
dátum javascriptu
Poradie zložitosti v programovacom jazyku C:
Pri programovaní v C závisí poradie zložitosti algoritmu od počtu operácií vykonaných programom. Napríklad, ak máme pole veľkosti n a chceme vyhľadať konkrétny prvok v poli, poradie zložitosti algoritmu bude závisieť od počtu prvkov v poli. Ak vykonáme a Lineárne vyhľadávanie cez pole bude Poradie zložitosti O(n) , čo znamená, že čas potrebný na vyhľadanie prvku sa lineárne zvýši s veľkosťou poľa. Ak použijeme a Binárny vyhľadávací algoritmus namiesto toho bude Rád zložitosti O (log n) , čo znamená, že čas potrebný na hľadanie prvku sa bude logaritmicky zvyšovať s veľkosťou poľa.
Podobne aj Poradie zložitosti iných algoritmov, ako napr Algoritmy triedenia , Grafové algoritmy , a Algoritmy dynamického programovania závisí aj od počtu operácií, ktoré program vykoná. Poradie zložitosti týchto algoritmov možno vyjadriť pomocou Veľký O notový zápis.
Pozrime sa na niektoré bežné rády zložitosti a ich zodpovedajúce algoritmy:
To znamená, že algoritmu trvá konštantný čas bez ohľadu na veľkosť vstupu. Napríklad prístup k prvku v poli trvá O(1) čas, pretože k prvku je možné pristupovať priamo pomocou jeho indexu.
To znamená, že čas potrebný na algoritmus sa logaritmicky zvyšuje s veľkosťou vstupu. Toto je bežne vidieť v Algoritmy rozdeľuj a panuj Páči sa mi to Binárne vyhľadávanie , ktoré rozdeľujú vstup na menšie časti na vyriešenie problému.
localdate
To znamená, že čas potrebný na algoritmus rastie lineárne s veľkosťou vstupu. Príklady takýchto algoritmov sú Lineárne vyhľadávanie a Bublinové triedenie .
To znamená, že čas potrebný na algoritmus sa zvýši o n vynásobený logaritmom n. Príklady takýchto algoritmov sú Rýchle triedenie a Mergesort .
To znamená, že čas potrebný na algoritmus sa zvyšuje kvadraticky s veľkosťou vstupu. Príklady takýchto algoritmov sú Bublinové triedenie a Triedenie vloženia .
To znamená, že čas potrebný na algoritmus sa zdvojnásobí s každým zvýšením veľkosti vstupu. Toto je bežne vidieť v Rekurzívne algoritmy ako Séria Fibonacci .
python __dict__
Je dôležité vedieť, že poradie zložitosti poskytuje iba hornú hranicu času potrebného na algoritmus. Skutočný čas môže byť oveľa kratší ako táto hranica, v závislosti od vstupných údajov a implementácie algoritmu.
Pri programovaní v jazyku C možno poradie zložitosti algoritmu určiť analýzou kódu a spočítaním počtu vykonaných operácií. Napríklad, ak máme cyklus, ktorý iteruje cez pole veľkosti n, časová zložitosť cyklu bude O(n) . Podobne, ak máme rekurzívnu funkciu, ktorá sa volá k-krát, časová zložitosť funkcie bude O(2^k) .
Na optimalizáciu výkonu programu je dôležité zvoliť algoritmy s nižším rádom zložitosti. Napríklad, ak potrebujeme triediť pole, mali by sme použiť triediaci algoritmus s nižším rádom zložitosti, ako napr. Rýchle triedenie alebo Mergesort , radšej než Bublinové triedenie , ktorý má vyšší rád zložitosti.
Analýza poradia zložitosti:
Aby sme analyzovali poradie zložitosti algoritmu, musíme určiť, ako rastie jeho prevádzkový čas alebo využitie priestoru so zvyšujúcou sa veľkosťou vstupu. Najbežnejšou metódou, ako to urobiť, je spočítať počet základných operácií vykonaných algoritmom.
heapify triediť
Základná operácia je operácia, ktorej vykonanie trvá konštantne dlho, ako napríklad pridanie dvoch čísel alebo prístup k prvku poľa. Počítaním počtu základných operácií vykonaných algoritmom ako funkcie veľkosti vstupu môžeme určiť jeho poradie zložitosti.
Zvážte napríklad nasledujúcu funkciu C, ktorá vypočítava súčet prvý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></=>