Algoritmus je posloupnost instrukcí, které jsou prováděny v předem určeném pořadí za účelem vyřešení problému nebo dokončení práce. Funkce je blok kódu, který lze volat a provádět z jiných částí programu.
Soubor pokynů pro vyřešení problému nebo provedení určité činnosti. V informatice se algoritmy používají pro širokou škálu operací, od základní matematiky až po složité zpracování dat.
Jedním z běžných algoritmů používaných v C je třídicí algoritmus. Algoritmus řazení uspořádá kolekci položek v určitém pořadí, například číselně nebo abecedně.
Existuje mnoho třídicích algoritmů, z nichž každý má své výhody a nevýhody. Nejběžnější třídicí algoritmy v C jsou quicksort, merge a sort.
Jednou z klíčových vlastností C je podpora ukazatelů. To umožňuje efektivní manipulaci s datovými strukturami, jako jsou pole, fronty atd. Díky tomu je vhodný pro implementaci algoritmů, které vyžadují komplexní manipulaci s daty, jako je třídění a algoritmické vyhledávání.
Jedním ze slavných příkladů softwarové knihovny implementované v C je standardní knihovna šablon (STL). Tato knihovna poskytuje širokou škálu algoritmů pro úkoly, jako je třídění, vyhledávání a manipulace s datovými strukturami.
Vlastnosti algoritmu
Definuje několik důležitých funkcí algoritmu, včetně:
Analýza algoritmů
Algoritmická analýza je proces hodnocení výkonnosti algoritmu z hlediska účinnosti, složitosti a dalších kritérií. Obvykle se to provádí za účelem vyhodnocení mnoha algoritmů a výběru optimálního řešení pro určitý problém nebo software.
Analýza algoritmů obvykle zahrnuje měření jejich časové a prostorové složitosti.
Stejně jako u prostorové složitosti, která popisuje potřebné množství paměti nebo místa na disku, časová složitost popisuje, jak dlouho algoritmus určí provedení úkolu.
Existují různé způsoby, jak analyzovat časovou složitost algoritmů, jako je zápis Big O a Omega. Symbol Omega poskytuje horní hranici časové složitosti algoritmu, zatímco symbol Omega poskytuje dolní hranici.
css středové tlačítko
Kromě měření časové a prostorové složitosti zahrnuje analýza algoritmů také další kritéria, jako je stabilita, paralelismus a škálovatelnost.
Zahrnují dva typy analýz.
oni jsou:-
- Předběžná analýza.
- Zadní analýza.
Předchozí analýza
Prior je metoda analýzy algoritmů, která se zaměřuje na odhadování výkonu algoritmu na základě jeho matematických vlastností, aniž by byl algoritmus skutečně prováděn.
Tento přístup vám umožňuje analyzovat časovou a prostorovou složitost algoritmů a dalších metrik bez nutnosti implementovat a spouštět algoritmy.
Zadní analýza
Na druhé straně zadní analýza je metoda analýzy algoritmu, která skutečně provádí algoritmus a měří jeho výkon.
Tento přístup poskytuje přesnější a podrobnější informace o výkonu algoritmu, ale vyžaduje implementaci a provedení algoritmu.
Složitost algoritmu
Algoritmická složitost je měřítkem pro měření účinnosti a výkonu algoritmu. Algoritmy jsou obvykle hodnoceny z hlediska času a prostoru potřebného k vyřešení problému nebo dosažení konkrétního cíle.
Ve složitosti algoritmu se používají dva faktory.
oni jsou:-
- Časový faktor.
- Prostorový faktor.
Časový faktor
- Množství času, který algoritmus potřebuje k provedení úkolu, se označuje jako časová složitost. Obvykle se měří počtem operací nebo kroků, které musí algoritmus provést, aby vyřešil problém.
- Časová složitost algoritmu je důležitá, protože určuje, jak dlouho trvá jeho provedení, a může mít významný dopad na výkon programu a systému.
- Časová složitost algoritmu může být vyjádřena pomocí notace Big O, což je způsob vyjádření horní hranice časové složitosti algoritmu.
- Algoritmus s časovou složitostí O(n) znamená, že čas potřebný ke spuštění algoritmu je přímo úměrný velikosti vstupních dat (n).
- Jiné běžné časové složitosti jsou O(n^2) kvadratická složitost a O(log n) logaritmická složitost.
Prostorová analýza
- Na druhou stranu, prostorová složitost se týká množství paměti nebo úložného prostoru potřebného k provedení algoritmu.
- To je důležité, protože určuje počet prostředků potřebných ke spuštění algoritmů, které mohou ovlivnit celkový výkon vaší aplikace nebo systému.
- Pokud je prostorová složitost algoritmu O(n), využívá množství paměti, které roste lineárně s velikostí vstupu.
- Pokud má algoritmus prostorovou složitost O(1), používá pevné množství paměti bez ohledu na velikost vstupu.
Jak napsat algoritmus
1. Nejprve definujte problém, který má algoritmus řešit.
Předpokládejme například, že chceme napsat algoritmus pro nalezení maximální hodnoty ze seznamu čísel.
2. Rozdělte problém na menší, zvládnutelné kroky.
- Inicializujte proměnnou 'max' na první hodnotu v seznamu.
- Pro každou následující hodnotu v seznamu porovnejte s 'max'.
- Pokud je hodnota větší než 'max', nastavte 'max' na tuto hodnotu.
- Pokračujte v tom, dokud nebudou porovnány všechny hodnoty v seznamu.
- Vrátí konečnou hodnotu „max“.
3. Napište svůj algoritmus v pseudokódu nebo v programovacím jazyce.
Algoritmus napsaný v pseudo kódu:
regexp_like v mysql
MAX (list) max = list[0] For i = 1 the length of the list list IF[i] > max max = list[i] End for Maximum return Maximum end
4. Otestujte svůj algoritmus, abyste se ujistili, že je správný a účinný.
Algoritmus můžete otestovat zadáním různých seznamů čísel a ověřením, že vrací maximální správnou hodnotu. Můžete také analyzovat časovou složitost vašeho algoritmu a určit, jak dobře se škáluje pro větší vstupy.
Příklad:-
Vstup: [1, 5, 2, 7, 3]
Výstup: 7.
Vysvětlení: 7 je maximální hodnota v seznamu.
5. Optimalizujte algoritmus.
Hledejte způsoby, jak optimalizovat algoritmy, aby byly rychlejší a efektivnější. To může zahrnovat úpravu pseudokódu nebo implementaci efektivnějších datových struktur nebo algoritmů.
Základní psaní algoritmů
Příklad: - Součet dvou celých čísel.
Krok 1 - Začít
Krok 2 - Deklarujte tři celá čísla a, b, c
Krok 3 - Definujte hodnoty aab
Krok 4 - Sečtěte hodnoty a a b
Krok 5 - Uložte výstup z kroku 4 v c
Krok 6 - Tisk c
Krok 7 - Stop
Typy algoritmů používaných v jazyce C.
1. Algoritmy řazení
C poskytuje bohatou sadu datových typů a operátorů, které lze použít k implementaci různých třídicích algoritmů, jako je bublinové třídění, vkládání a rychlé třídění.
Tyto algoritmy jsou užitečné v mnoha aplikacích, protože je lze použít k třídění dat různých velikostí a typů.
Existují různé třídicí algoritmy.
oni jsou:-
(i) Bublinové řazení: Nekomplikovaný třídicí algoritmus, který opakovaně porovnává blízké komponenty a vypíná je, pokud jsou mimo provoz.
Algoritmus pro bublinové řazení je:-
- Začněte s netříděným seznamem prvků.
- Porovnejte první dva prvky v seznamu. Pokud je první prvek větší než druhý, prohoďte je.
- Přejděte na další dvojici prvků a opakujte krok 2, dokud nedosáhnete konce seznamu.
- Pro každou položku v seznamu opakujte kroky 2 a 3 ještě jednou. které se říká propustky.
- Opakujte kroky 2-4 pro celý seznam. Jak budete opakovat průchody, prvky „bublají“ na svou správnou pozici v seřazeném seznamu.
- Jakmile je průchod dokončen a neprovedou se žádné swapy, seznam se seřadí a algoritmus se může zastavit.
- Vrátí se konečný seřazený seznam.
(ii) Druh vložení : metoda řazení, která vytváří setříděný seznam po jednotlivých prvcích umístěním každého z nich na příslušné místo.
Algoritmus pro řazení vložení je:-
- Inicializujte prázdný seřazený seznam a nesetříděný seznam prvků, které mají být seřazeny.
- První člen z neseřazeného seznamu by měl být vzat a umístěn na příslušnou pozici v seřazeném seznamu.
- Opakujte krok 2 pro každý následující prvek v neseřazeném seznamu.
- Porovnejte aktuální prvek s prvky v seřazeném seznamu, počínaje prvkem bezprostředně vlevo.
- Prohoďte dva prvky, pokud je aktuální prvek menší než prvek nalevo od něj.
- Pokud je aktuální prvek větší než prvek nalevo, vložte jej na správné místo v seřazeném seznamu.
- Opakujte kroky 4-6 pro každý následující prvek v neseřazeném seznamu.
- Jakmile budou všechny prvky zpracovány, setříděný seznam bude obsahovat všechny prvky ve správném pořadí.
- Proces třídění je dokončen.
(iii) Třídění výběru : metoda řazení, která konzistentně zahajuje seřazený výpis s nejmenším detailem z neuspořádaného výpisu.
Algoritmus pro řazení výběru je:-
- Začněte nastavením primárního prvku seznamu jako prvku min.
- Opakujte přes zbývající položky v seznamu a porovnejte každou z nich s aktuálním minimem.
- Pokud se zjistí, že prvek je menší než stávající, nastavte nové minimum.
- Změňte aktuální minimum na první prvek seznamu, kdykoli dosáhne svého závěru.
- Pro zbývající neseřazenou část výpisu opakujte kroky 2-4, ale začněte s druhou položkou na seznamu (protože první prvek je již seřazen).
- Pokračujte v řazení seznamu tímto způsobem, dokud nebude celý seřazen.
(iv) Rychlé třídění : Algoritmus řazení rozděl a panuj, který vybere prvek pivotu a rozdělí seznam na podseznamy v závislosti na tom, zda je prvků méně nebo více než pivot. Poté se podseznamy opakovaně třídí, dokud není seřazen celý seznam.
Algoritmus pro rychlé řazení je:-
- Vyberte prvek pivotu ze seznamu. Toto je obvykle první prvek, ale může to být také náhodný prvek nebo medián seznamu.
- Rozdělte seznam na dva dílčí seznamy: jeden obsahuje prvky menší než pivot a druhý obsahuje prvky větší než pivot.
- Rekurzivně seřaďte podseznam obsahující prvky méně než pivot pomocí stejného procesu.
- Stejný postup použijte k rekurzivnímu řazení podseznamu položek větších, než je pivot.
- Spojte seřazené dílčí seznamy s prvkem pivot mezi nimi a vytvořte plně seřazený seznam.
- Vraťte úplně seřazený seznam.
(v) Lot jde : Algoritmus řazení rozděl a panuj rozdělí seznam na dvě poloviny, každou polovinu seřadí a poté obě poloviny v seřazeném pořadí spojí.
Algoritmus řazení sloučení:
- Vytvořte ze seznamu dva dílčí seznamy: jeden s prvky pod pivotem a druhý s prvky nad pivotem.
- Vytváří nový seřazený podseznam opakovaným slučováním podseznamů, dokud neexistuje pouze jeden podseznam. Toto bude váš seřazený seznam.
- Kroky ke sloučení dvou podadresářů:-
- Vytvořte prázdný seznam, který bude obsahovat seřazené prvky.
- Porovná první prvek každého dílčího seznamu.
- Přidá menší prvek do nového seznamu a odebere jej z nadřazeného dílčího seznamu.
- Opakujte kroky 2 a 3, dokud nebude seznam zcela prázdný.
- Přidá zbývající prvky z jiných dílčích seznamů do nového seznamu.
- Nahradí sloučený dílčí seznam novým seřazeným seznamem.
- Tento postup opakujte, dokud nebudou všechny dílčí seznamy sloučeny do jednoho seřazeného seznamu.
(vi) Řazení haldy : Algoritmus řazení, který třídí prvky pomocí datové struktury zvané halda.
Toto je klasifikační algoritmus:
- Naskládejte zbytek prvků. Počínaje kořenem je každý uzel porovnáván se svými potomky a vyměňovat uzly se svými staršími potomky, dokud není splněna vlastnost max haldy.
- Opakujte kroky 2 a 3 s nově naskládanými prvky, kromě posledního prvku ve správné poloze.
- Tento postup opakujte, dokud v zásobníku nezůstane pouze jeden prvek. Toto je nyní seřazeny.
(vii) Radix sort : Třídicí algoritmus, který třídí prvky na základě číslic nebo číslic jejich binární reprezentace.
Algoritmus pro řazení Radix je:-
skvělý počítačový jazyk
- určit, kolik číslic je obsaženo v největším prvku vstupního výpisu.
- Inicializujte proměnnou, řekněme místo číslice, na 1, která představuje aktuální místo číslice.
- Vytvořte prázdný seznam pro každou možnou číselnou hodnotu od 0 do 9.
- Iterujte seznam vstupů a přidejte každý prvek do příslušného seznamu na základě hodnoty aktuálního místa číslice.
- Spojte všechny seznamy dohromady a vytvořte nový seznam v pořadí číselných seznamů.
- Vynásobením digitPlace 10 se přesunete na další číslici.
- Opakujte kroky 4-6 pro každé místo číslice, dokud nebudou zohledněny všechny číslice v největším prvku.
- Konečný seznam bude seřazen vzestupně podle číslic prvků.
- Vraťte konečný seřazený seznam.
2. Vyhledávací algoritmy
C také poskytuje nástroje potřebné k implementaci různých vyhledávacích algoritmů, jako je lineární vyhledávání a binární vyhledávání. Tyto algoritmy dokážou rychle najít konkrétní položky v sadě dat, díky čemuž jsou užitečné pro širokou škálu aplikací.
Existuje mnoho typů vyhledávacích algoritmů.
Oni jsou:-
(i) Lineární vyhledávání : Základní vyhledávací algoritmus, který zkoumá každou položku ve výpisu jednu po druhé, dokud nenajde požadovanou položku.
Algoritmus pro lineární vyhledávání:-
- Definujte vstup pro algoritmus: Vstupem pro algoritmus lineárního vyhledávání je seznam prvků (nebo pole) a cílový prvek, který hledáme.
- Inicializujte proměnnou s názvem 'index' na -1: Tato proměnná bude použita k uložení indexu cílového prvku, pokud bude nalezen.
- Procházení seznamu prvků: Začněte od prvního prvku a zkontrolujte každý prvek v seznamu jeden po druhém.
- Porovnejte přítomný prvek s požadovaným prvkem pro vyhodnocení: Ponechte index aktuálního prvku v proměnné index a opusťte smyčku, pokud jsou moderní prvek a prvek cíle identické.
- Vraťte index cílového prvku: Po dokončení cyklu vraťte hodnotu uloženou v proměnné index. Pokud cílový prvek není nalezen, bude hodnota indexu -1.
(ii) Binární vyhledávání : Algoritmus vyhledávání, který funguje tak, že rozděluje výpis na poloviny a vyhledává v rámci těchto polovin, bude pravděpodobně obsahovat prvek.
Algoritmus pro binární vyhledávání:-
- Vstup: Seřazený seznam n prvků a cílový prvek x.
- Inicializace proměnných: Nastavte nízký index na 0, vysoký index na n-1 a střední na (nízký+vysoký)/2.
- Spuštění smyčky: Zatímco je nízký index menší nebo roven vysokému indexu, opakujte následující kroky.
- Porovnejte střední prvek s x: Pokud je střední prvek roven x, vrátí střední index.
- Aktualizujte nízký nebo vysoký index: Pokud je x větší než střední prvek, nastavte nízký index na střední + 1. Jinak nastavte vysoký index na střední - 1.
- Aktualizujte střední index: Střední = (nízký+vysoký)/2.
- Konec cyklu: Pokud je nízký index větší než vysoký index, pak x není v seznamu a algoritmus vrátí chybu.
- Výstup: Index x v seznamu nebo chybové zprávě.
(iii) Prohledávání do hloubky : Algoritmus vyhledávání, který zkoumá každou větev tak daleko, jak je to možné, než se otočí.
Pro hloubkové vyhledávání platí následující pokyny:
- vyberte počáteční vrchol nebo uzel grafu, se kterým chcete začít.
- Přidejte značku návštěv k prvnímu vrcholu.
- Umístěte počáteční vrchol přímo do zásobníku.
- Dokud nebude zásobník prázdný, opakujte následující akce: -
- Odstraňte horní vrchol zásobníku.
- Označte jako navštívené a vložte do zásobníku každého nenavštíveného souseda vyskočeného vrcholu.
- Pokračujte v tomto procesu, dokud nenavštívíte všechny vrcholy v grafu.
- Jakmile byly navštíveny všechny vrcholy, algoritmus je dokončen a v grafu se provede hloubkové prohledávání.
(iv) Prohledávání do šířky : Algoritmus vyhledávání, který prozkoumá všechny sousedy uzlu před přechodem na další úroveň.
halda a halda třídit
Algoritmus pro vyhledávání do šířky je:-
- Začněte s kořenovým uzlem nebo počátečním stavem.
- Přidejte kořenový uzel do fronty.
- Zkontrolujte, zda je fronta prázdná; pokud ano, ukončete algoritmus.
- Vezměte první prvek z fronty a označte jej jako navštívený.
- Rozšiřte současný uzel přidáním všech jeho nenavštívených sousedů do fronty.
- Dokud není požadovaný uzel nalezen nebo fronta prázdná, opakujte kroky 3 až 5.
- Vraťte cestu z předběžného stavu do cílového stavu, pokud je nalezen cílový uzel.
- Pokud je fronta prázdná, ukončete sadu pravidel a nahlaste, že stav cíle nebyl identifikován.
(v) Hledání interpolace : Algoritmus vyhledávání, který používá hodnoty hledaných prvků k odhadu pozice v indexu.
Je důležité, aby pole bylo rovnoměrně rozloženo. Jinak je to algoritmus.
Funguje podle očekávání.
Algoritmus lze shrnout následovně.
- Získejte seznam vstupů a klíčovou hodnotu pro vyhledávání.
- Inicializujte dolní a horní proměnné na prvním a posledním indexu seznamu.
- Pokud je nižší hodnota menší nebo rovna vyšší hodnotě, pak:-
- Vypočítejte odhadovanou polohu pomocí následujícího vzorce:
pos = nízká + ((vysoká - nízká) / (arr[vysoká] - arr[nízká])) * (x - arr[nízká]). - Vraťte pozici, pokud je odhadovaná hodnota pozice klíčovou hodnotou.
- c) Pokud je odhadovaná hodnota pozice nižší než hodnota klíče, nastavte ji níže.
Pozice + 1. - d) Pokud je hodnota odhadované pozice větší než hodnota klíče Set, pozice - 1 nahoru.
- Vypočítejte odhadovanou polohu pomocí následujícího vzorce:
- Pokud hodnota klíče není nalezena, vraťte hodnotu -1, abyste označili, že hodnota není v seznamu.
(vi) Vyhledávání skokem : Metoda vyhledávání, která iteruje seznam v krocích konstantní délky, dokud nenajde relevantní prvek nebo nezjistí, že již není přítomen.
Algoritmus hledání skoku je následující:
- Nejprve nastavte velikost skoku na druhou odmocninu počtu prvků pole.
- Nastaví proměnnou s názvem 'current' na první prvek pole.
- Iteruje pole přeskakováním podle velikosti skoku při inkrementaci proměnné nazvané „skok“.
- Pokud je stávající prvek menší než požadovaný prvek, přejděte k následujícímu skoku.
- Pokud je aktuální prvek větší než cílový prvek, proveďte lineární vyhledávání mezi aktuálním prvkem a předchozím prvkem skoku, abyste našli cílový prvek.
- Pokud cílový prvek není v poli nalezen, vrátí hodnotu -1, což znamená, že v poli není.
- Pokud je prvek nalezen, vrátí index prvku v poli.
3. Grafové algoritmy
Díky podpoře ukazatelů a datových struktur, jako jsou pole a propojené seznamy, je C vhodný pro implementaci algoritmů, které manipulují s grafy, jako je hledání nejkratší cesty mezi dvěma uzly v grafu.
Existují různé typy grafových algoritmů.
oni jsou:-
4. Kryptografické algoritmy
C podporuje nízkoúrovňové operace a efektivní manipulaci s daty, takže je ideální pro implementaci algoritmů používaných v kryptografii, jako jsou šifrovací a dešifrovací algoritmy.
Existují různé typy šifrovacích algoritmů.
Oni jsou:-
Výhody algoritmu
Algoritmy mají mnoho výhod.
oni jsou:-
Nevýhody algoritmu
Algoritmy jsou velmi užitečné pro programování, ale mají své nevýhody.
oni jsou:-