Algoritmus je krok-za-krokem postup, který definuje sadu instrukcí, které mají být provedeny v určitém pořadí získat požadovaný výstup. Algoritmy jsou obecně vytvářeny nezávisle na základních jazycích, tj. algoritmus může být implementován ve více než jednom programovacím jazyce.,
z hlediska struktury dat následují některé důležité kategorie algoritmů-
-
vyhledávací algoritmus pro vyhledávání položky v datové struktuře.
-
Sort − algoritmus pro řazení položek v určitém pořadí.
-
Insert − algoritmus pro vložení položky do datové struktury.
-
Update − algoritmus pro aktualizaci existující položky v datové struktuře.
-
Delete − algoritmus pro odstranění existující položky z datové struktury.
vlastnosti algoritmu
ne všechny postupy lze nazvat algoritmem., Algoritmus by měl mít následující vlastnosti −
-
jednoznačný-algoritmus by měl být jasný a jednoznačný. Každý z jeho kroků (nebo fází) a jejich vstupy/výstupy by měly být jasné a musí vést pouze k jednomu významu.
-
vstup-algoritmus by měl mít 0 nebo více dobře definovaných vstupů.
-
výstup-algoritmus by měl mít 1 nebo více dobře definovaných výstupů a měl by odpovídat požadovanému výstupu.
-
konečnost − algoritmy musí skončit po konečném počtu kroků.,
-
proveditelnost-by měla být proveditelná s dostupnými zdroji.
-
Independent-algoritmus by měl mít podrobné pokyny, které by měly být nezávislé na jakémkoli programovacím kódu.
Jak napsat algoritmus?
neexistují žádné dobře definované standardy pro psaní algoritmů. Spíše je závislý na problémech a zdrojích. Algoritmy nejsou nikdy napsány na podporu konkrétního programovacího kódu.
jak víme, že všechny programovací jazyky sdílejí základní konstrukty kódu, jako jsou smyčky (do, for, while), flow-control (if-else) atd., Tyto běžné konstrukty lze použít k napsání algoritmu.
algoritmy zapisujeme krok za krokem, ale není tomu tak vždy. Psaní algoritmů je proces a provádí se poté, co je problémová doména dobře definována. To znamená, že bychom měli znát problémovou doménu, pro kterou navrhujeme řešení.
příklad
zkusme se naučit psaní algoritmů pomocí příkladu.
problém-Navrhněte algoritmus pro přidání dvou čísel a zobrazení výsledku.
Step 1 − STARTStep 2 − declare three integers a, b & cStep 3 − define values of a & bStep 4 − add values of a & bStep 5 − store output of step 4 to cStep 6 − print cStep 7 − STOP
algoritmy říkají programátorům, jak program kódovat., Alternativně lze algoritmus zapsat jako –
Step 1 − START ADDStep 2 − get values of a & bStep 3 − c ← a + bStep 4 − display cStep 5 − STOP
při návrhu a analýze algoritmů se obvykle používá druhá metoda k popisu algoritmu. Pro analytika je snadné analyzovat algoritmus ignorující všechny nežádoucí definice. Může sledovat, jaké operace se používají a jak proces proudí.
psaní krokových čísel je volitelné.
navrhujeme algoritmus pro získání řešení daného problému. Problém lze vyřešit více než jedním způsobem.,
proto lze pro daný problém odvodit mnoho algoritmů řešení. Dalším krokem je analyzovat tyto navrhované algoritmy řešení a implementovat nejvhodnější řešení.
analýza algoritmu
účinnost algoritmu může být analyzována ve dvou různých fázích, před implementací a po implementaci. Jsou to následující –
-
A Priori analýza-jedná se o teoretickou analýzu algoritmu., Účinnost algoritmu je měřeno za předpokladu, že všechny ostatní faktory, například rychlost procesoru, jsou konstantní a nemají žádný vliv na provádění.
-
a Posterior Analysis-jedná se o empirickou analýzu algoritmu. Vybraný algoritmus je implementován pomocí programovacího jazyka. To se pak provádí na cílovém počítači. V této analýze se shromažďují skutečné statistiky, jako je požadovaný čas běhu a prostor.
dozvíme se o analýze algoritmu a priori., Analýza algoritmů se zabývá dobou provádění nebo běhu různých operací. Provozní doba operace může být definována jako počet počítačových instrukcí provedených na operaci.
Algoritmus Složitost
Předpokládejme, že X je algoritmus, a n je velikost vstupních dat, času a prostoru používá algoritmus X jsou dva hlavní faktory, které rozhodují o účinnosti X.
-
Faktor Času − Čas je měřen pomocí počítání množství klíčových operací, jako je porovnávání, třídění algoritmus.,
-
prostorový faktor-prostor se měří počítáním maximálního paměťového prostoru požadovaného algoritmem.
složitost algoritmu f (n)udává provozní čas a/nebo úložný prostor požadovaný algoritmem z hlediska n jako velikost vstupních dat.
prostorová složitost
prostorová složitost algoritmu představuje množství paměťového prostoru požadovaného algoritmem v jeho životním cyklu., Prostor potřebný algoritmu je roven součtu těchto dvou složek,
-
fixní část, která je prostor potřebný k ukládání určitých dat a proměnných, které jsou nezávislé na velikosti problému. Například použité jednoduché proměnné a konstanty, velikost programu atd.
-
proměnná část je prostor požadovaný proměnnými, jehož velikost závisí na velikosti problému. Například dynamická alokace paměti, rekurze stack space atd.,
prostorové složitosti S(P) algoritmus P S(P) = C + SP(I), kde C je pevná část a S(I) je proměnná část algoritmu, který závisí na stupni charakteristické I Následující jednoduchý příklad, který se snaží vysvětlit koncept −
Algorithm: SUM(A, B)Step 1 - STARTStep 2 - C ← A + B + 10Step 3 - Stop
Tady máme tři proměnné A, B, a C a konstantní. Proto S (P) = 1 & plus; 3. Nyní prostor závisí na datových typech daných proměnných a konstantních typech a bude odpovídajícím způsobem vynásoben.,
časová složitost
časová složitost algoritmu představuje množství času potřebného algoritmem k dokončení. Časové požadavky lze definovat jako číselnou funkci T (n), kde T(n) lze měřit jako počet kroků za předpokladu, že každý krok spotřebovává konstantní čas.
například přidání dvou n-bitových celých čísel trvá n kroky. V důsledku toho je celkový výpočetní čas T (n) = c ∗ n, kde c je čas potřebný pro přidání dvou bitů. Zde pozorujeme, že T(n) roste lineárně, jak se zvyšuje velikost vstupu.,