Datové struktury a algoritmy (DSA) odkazují na studium metod organizace a ukládání dat a návrh procedur (algoritmů) pro řešení problémů, které na těchto datových strukturách pracují. DSA je jednou z nejdůležitějších dovedností, kterou musí mít každý student informatiky. Často je vidět, že lidé s dobrými znalostmi těchto technologií jsou lepšími programátory než ostatní, a tak prolomí rozhovory téměř každého technologického giganta. Tento Výukový program DSA si klade za cíl pomoci vám rychle a snadno se naučit datové struktury a algoritmy (DSA).

Obsah

• Úplný formulář DSA
• Co je DSA?
• Jak se naučit DSA?
• Tětiva
• Propojené seznamy
• Matice/Mřížka
• Zásobník
• Fronta
• Halda
• hash
• Strom
• Graf

• Algoritmus hledání
• Algoritmus řazení
• Algoritmus rozděl a panuj
• Chamtivé algoritmy
• Rekurze
• Algoritmus zpětného sledování
• Dynamické programování
• Algoritmy grafů:
• Hledání vzoru
• Matematické algoritmy
• Geometrické algoritmy
• Bitové algoritmy
• Randomizované algoritmy
• Branch and Bound Algorithm

Úplný formulář DSA

Termín DSA znamená Datové struktury a algoritmy , v kontextu informatiky.

Co je DSA?

Datové struktury a algoritmy (DSA) odkazují na studium metod organizace a ukládání dat a návrh procedur (algoritmů) pro řešení problémů, které na těchto datových strukturách pracují.

Jak se naučit DSA?

První a nejdůležitější věcí je rozdělení celkového postupu na malé kousky, které je třeba provést postupně. Celý proces učení DSA od nuly lze rozdělit do 5 částí:

1. Naučte se alespoň jeden programovací jazyk (Necháme to na vašem výběru.)
2. Naučte se datové struktury
3. Naučte se algoritmy
4. Přečtěte si o složitosti času a prostoru
5. Cvičné problémy na DSA

Jak se naučit DSA?

Doufáme, že jste se naučili programovací jazyk podle svého výběru, pojďme se posunout vpřed dalším krokem k naučení DSA v tomto tutoriálu DSA.

Zde přichází nejdůležitější a nejočekávanější fáze plánu pro učení struktury dat a algoritmu – fáze, kdy se začnete učit o DSA. Téma DSA se skládá ze dvou částí:

• Datové struktury
• Algoritmy

Ačkoli jsou to dvě různé věci, jsou velmi propojené a je velmi důležité sledovat správnou cestu, abyste se je naučili co nejefektivněji. Pokud nevíte, který z nich se naučit jako první, doporučujeme vám projít si naši podrobnou analýzu na toto téma: Zde jsme sledovali tok učení datové struktury a poté nejpříbuznější a nejdůležitější algoritmy používané touto datovou strukturou.

Naučte se datové struktury

Datové struktury jsou základní komponenty, které pomáhají efektivně organizovat a ukládat data do paměti počítače. Poskytují způsob, jak efektivně spravovat data a manipulovat s nimi, což umožňuje rychlejší operace přístupu, vkládání a mazání. Mezi běžné datové struktury patří pole, propojené seznamy, zásobníky, fronty, stromy a grafy , z nichž každá slouží specifickým účelům na základě požadavků daného problému. Pochopení datových struktur je základem pro navrhování účinných algoritmů a optimalizaci výkonu softwaru.

Pole je lineární datová struktura, která ukládá kolekci prvků stejného datového typu. Prvky mají přidělenou souvislou paměť, což umožňuje přístup v konstantním čase. Každý prvek má jedinečné indexové číslo.

• Operace na poli:
  • Průjezd : Iterace přes prvky pole.
  • Vložení : Přidání prvku do pole na konkrétním indexu.
  • Vymazání : Odebrání prvku z pole na určitém indexu.
  • Hledání : Hledání prvku v poli podle jeho hodnoty nebo indexu.
• Typy polí :
  • Jednorozměrné pole : Jednoduché pole s jedním rozměrem.
  • Vícerozměrné pole : Pole s více rozměry, jako je matice.
• Aplikace Array :
  • Ukládání dat sekvenčním způsobem
  • Implementace front, zásobníků a dalších datových struktur
  • Reprezentující matice a tabulky
• Související témata na poli:
  • Výukový program pro pole
  • 50 hlavních problémů s kódováním pole pro rozhovory
  • Procvičte si problémy na polích

2. Řetězec

A tětiva je posloupnost znaků, která se obvykle používá k reprezentaci textu. Je považován za datový typ, který umožňuje manipulaci a zpracování textových dat v počítačových programech.

• Operace na řetězci :
  • Zřetězení : Spojení dvou řetězců dohromady.
  • Srovnání : Porovnání dvou řetězců lexikograficky.
  • Podřetězec extrakce : Extrahování podřetězce z řetězce.
  • Vyhledávání : Hledání podřetězce v řetězci.
  • Modifikace : Změna nebo nahrazení znaků v řetězci.
• Aplikace String :
  • Zpracování textu
  • Shoda vzorů
  • Ověření dat
  • Správa databáze
• Související příspěvky:
  • Strunový návod
  • 50 hlavních problémů s kódováním řetězců pro rozhovory
  • Cvičné problémy na provázku

3. Propojené seznamy

A spojový seznam je lineární datová struktura, která ukládá data do uzlů, které jsou propojeny ukazateli. Na rozdíl od polí nejsou propojené seznamy uloženy v souvislých paměťových místech.

• Charakteristika propojeného seznamu:
  • Dynamický : Velikost propojených seznamů lze snadno změnit přidáním nebo odebráním uzlů.
  • Nesouvislé : Uzly jsou uloženy v náhodných paměťových místech a propojeny ukazateli.
  • Sekvenční přístup : K uzlům lze přistupovat pouze postupně, počínaje od začátku seznamu.
• Operace na propojeném seznamu:
  • Stvoření : Vytvoření nového propojeného seznamu nebo přidání nového uzlu do existujícího seznamu.
  • Průjezd : Iterování seznamu a přístup ke každému uzlu.
  • Vložení : Přidání nového uzlu na konkrétní pozici v seznamu.
  • Vymazání : Odebrání uzlu ze seznamu.
  • Vyhledávání : Hledání uzlu s konkrétní hodnotou v seznamu.
• Typy propojeného seznamu :
  • Jednotlivě propojený seznam : Každý uzel ukazuje na další uzel v seznamu.
  • Dvojitě propojený seznam : Každý uzel ukazuje na další i předchozí uzel v seznamu.
  • Kruhový propojený seznam : Poslední uzel ukazuje zpět na první uzel a tvoří kruhovou smyčku.
• Aplikace Linked List :
  • Propojené seznamy se používají v různých aplikacích, včetně:
  • Implementace front a zásobníků
  • Reprezentace grafů a stromů
  • Udržování objednaných dat
  • Správa paměti
• Související témata:
  • Výukový program propojeného seznamu
  • 50 hlavních problémů na propojeném seznamu pro rozhovory
  • Procvičte si problémy na propojených seznamech

4. Matice/Mřížka

A matice je dvourozměrné pole prvků, uspořádaných do řádků a sloupců. Je reprezentován jako obdélníková mřížka s každým prvkem na průsečíku řádku a sloupce.

• Klíčové koncepty:
  • Řádky : Vodorovné čáry prvků v matici.
  • Sloupce : Svislé čáry prvků v matici.
  • Rozměry : Počet řádků a sloupců v matici (např. matice 3×4 má 3 řádky a 4 sloupce).
  • Živel Přístup : K prvkům lze přistupovat pomocí řádkových a sloupcových indexů (např. M[2][3] odkazuje na prvek v řádku 2, sloupci 3).
• Aplikace Matrix/Grid :
  • Zpracování obrazu
  • Analýza dat
  • Problémy s optimalizací
• Související příspěvky:
  • Výukový program Matrix/Mřížka
  • 50 nejlepších problémů na matici/mřížce pro rozhovory
  • Cvičné problémy na matici/mřížce

5. Zásobník

Zásobník je lineární datová struktura, která sleduje určité pořadí, ve kterém jsou operace prováděny. Objednávka může být LIFO (Last In First Out) nebo FILO (First In Last Out) . LIFO znamená, že prvek, který je vložen jako poslední, vyjde jako první a ŘÁDEK znamená, že prvek, který je vložen jako první, vyjde jako poslední.

• Operace na Stacku :
  • TAM : Přidá prvek do horní části zásobníku
  • Pop : Odebere a vrátí prvek v horní části zásobníku
  • Podívejte se : Vrátí prvek v horní části zásobníku, aniž by jej odstranil
  • Velikost : Vrátí počet prvků v zásobníku
  • Je prázdný : Zkontroluje, zda je zásobník prázdný
• Aplikace Stack :
  • Volání funkcí
  • Hodnocení výrazů
  • Zpětné sledování
  • Operace zpět/znovu
• Související témata na Stack:
  • Výukový program zásobníku
  • Top 50 problémů v zásobníku pro rozhovory
  • Procvičte si problémy na Stacku

6. Fronta

A Fronta Struktura dat je základní koncept v informatice používaný pro ukládání a správu dat v určitém pořadí. Řídí se principem První dovnitř, první ven ( FIFO ), kde první prvek přidaný do fronty je první, který má být odstraněn

• Operace ve frontě :
  • Zařadit do fronty : Přidá prvek do zadní části fronty
  • V souladu s tím : Odebere prvek z přední části fronty
  • Podívejte se : Obnoví přední prvek bez jeho odstranění
  • Je prázdný : Kontroluje, zda je fronta prázdná
  • Je plný : Kontroluje, zda je fronta plná
• Typ fronty :
  • Kruhová fronta : Poslední prvek se připojí k prvnímu prvku
  • Oboustranná fronta (Deque) : Operace lze provádět z obou konců
  • Prioritní fronta : Prvky jsou uspořádány podle priority
• Aplikace Queue :
  • Plánování práce
  • Řazení zpráv do fronty
  • Simulační modelování
  • Ukládání dat do vyrovnávací paměti
• Související témata:
  • Výukový program fronty
  • 50 největších problémů ve frontě na pohovory
  • Procvičte si problémy ve frontě

7. Halda

A Halda je kompletní binární stromová datová struktura, která splňuje vlastnost haldy: pro každý uzel je hodnota jeho potomků menší nebo rovna jeho vlastní hodnotě. K implementaci se obvykle používají haldy prioritní fronty , kde nejmenší (nebo největší) prvek je vždy u kořene stromu.

• Operace haldy :
  • Vložit : Přidá nový prvek do haldy při zachování vlastností haldy.
  • Extrakt-Max/Extract-Min : Odebere kořenový prvek a restrukturalizuje haldu.
  • Tlačítko zvýšení/snížení : Aktualizuje hodnotu uzlu a restrukturalizuje haldu.
• Typy haldy :
  • Max-Hroma : Kořenový uzel má mezi svými potomky maximální hodnotu.
  • Min-Hromad : Kořenový uzel má mezi svými potomky minimální hodnotu.
• Aplikace haldy :
  • Prioritní fronty
  • Řazení
  • Grafové algoritmy (např. Dijkstrův algoritmus)
• Související příspěvky:
  • Výuka haldy
  • Top 50 problémů na hromadě pro rozhovory
  • Cvičné problémy na haldě

8. hash

Hašování je technika, která generuje výstup s pevnou velikostí (hodnotu hash) ze vstupu proměnné velikosti pomocí matematických vzorců tzv. hashovací funkce . Hašování se používá k určení indexu nebo umístění pro uložení položky v datové struktuře, což umožňuje efektivní vyhledávání a vkládání.

• Klíčové koncepty:
  • Hashovací funkce : Matematická funkce, která mapuje vstup na hodnotu hash.
  • Tabulka hash : Datová struktura, která ukládá páry klíč–hodnota, kde klíč je hodnota hash a hodnota jsou skutečná data.
  • Kolize : Když dva různé klíče vytvářejí stejnou hodnotu hash.
• Typy hashovacích funkcí :
  • Metoda dělení : Vydělí vstup konstantou a zbytek použije jako hash hodnotu.
  • Střední náměstí Metoda: Učiní druhou mocninu vstupu a vezme střední číslice jako hash hodnotu.
  • Metoda skládání : Rozdělí vstup do bloků stejné velikosti a sečte je, aby se získala hodnota hash.
  • Metoda násobení : Vynásobí vstup konstantou a použije zlomkovou část jako hodnotu hash.

• Techniky řešení kolize :
  • Oddělené řetězení (otevřené hašování) : Uloží kolidující prvky v propojeném seznamu s odpovídající hodnotou hash.
  • Otevřené adresování (uzavřené hašování) : Používá různé strategie k nalezení alternativního umístění pro kolidující prvky v tabulce hash.
• Aplikace hashování :
  • Efektivní ukládání a načítání dat v databázích a souborových systémech.
  • Ověřování hesel a digitálních podpisů.
  • Distribuce požadavků na více serverů.
  • Generování bezpečných hashů pro integritu dat a ověřování.
• Související příspěvky:
  • Výukový program hash
  • Praktické problémy s hašováním

9. Strom

A strom je nelineární hierarchická datová struktura skládající se z uzlů spojených hranami, přičemž horní uzel se nazývá kořen a uzly mají podřízené uzly. Používá se v informatice pro efektivní organizaci dat.

jedinečný klíč mysql

• Přechod stromu : Metody procházení stromů se používají k návštěvě a zpracování uzlů ve stromové datové struktuře. Tři běžné způsoby procházení jsou:
  • V pořádku : Navštivte levý podstrom, aktuální uzel a poté pravý podstrom.
  • Předobjednávka : Navštivte aktuální uzel, levý podstrom, poté pravý podstrom.
  • Po objednání : Navštivte levý podstrom, pravý podstrom a poté aktuální uzel.
• Klasifikace stromů:
  • Klasifikace Stromy odkazují na seskupování stromů na základě určitých charakteristik nebo kritérií. To může zahrnovat kategorizaci stromů na základě jejich faktoru rovnováhy, stupně uzlů, vlastností řazení atd. Níže jsou uvedeny některé důležité klasifikace stromu.

• Aplikace stromů:
  • Souborové systémy
  • Databáze
  • XML dokumenty
  • Umělá inteligence
• Související příspěvky:
  • Výukový program pro strom
  • 50 nejčastějších problémů s kódováním stromu
  • Procvičte si problémy na stromě

10. Graf

A Graf je nelineární datová struktura sestávající z konečné množiny vrcholů (nebo uzlů) a množiny hran, které spojují dvojici uzlů.

• Průchody grafu:
  • Breadth-First Search (BFS) : Navštěvuje uzly úroveň po úrovni.
  • Hloubkové vyhledávání (DFS) : Navštěvuje uzly rekurzivně, přičemž prozkoumává jednu větev po druhé.
• Aplikace grafů :
  • Sociální sítě
  • Mapy a navigace
  • Plánování
  • Dolování dat
• Související příspěvky:
  • Grafické znázornění
  • Typy grafů
  • Výukový program pro grafy
  • Procvičte si úlohy na grafu

Naučte se algoritmy

Jakmile si vyjasníte pojmy Datové struktury , nyní je čas začít svou cestu přes Algoritmy . Na základě typu povahy a použití jsou algoritmy seskupeny do několika kategorií, jak je uvedeno níže:

1. Algoritmus hledání

Vyhledávací algoritmy se používají k vyhledání konkrétních dat v rámci větší sady dat. Pomáhá najít přítomnost cílové hodnoty v datech. Existují různé typy vyhledávacích algoritmů, z nichž každý má svůj vlastní přístup a efektivitu.

• Nejběžnější vyhledávací algoritmy:
  • Lineární vyhledávání : Iterativní vyhledávání z jednoho konce na druhý.
  • Binární vyhledávání : Vyhledávání rozděl a panuj v setříděném poli, přičemž se při každé iteraci zmenší prostor pro vyhledávání na polovinu.
  • Ternární vyhledávání : Vyhledávání rozděl a panuj v setříděném poli, přičemž v každé iteraci rozděluje vyhledávací prostor na tři části.
• Další vyhledávací algoritmy:
  • Skokové vyhledávání
  • Hledání interpolace
  • Exponenciální vyhledávání
• Související témata:
  • Procvičte si úlohy na vyhledávacím algoritmu

2. Algoritmus řazení

Algoritmy řazení se používají k uspořádání prvků seznamu v určitém pořadí, jako je numerické nebo abecední. Organizuje položky systematickým způsobem, což usnadňuje vyhledávání a přístup ke konkrétním prvkům.

Existuje mnoho různých typů třídicích algoritmů. Některé široce používané algoritmy jsou:

Související témata:

• Výukový program algoritmu řazení
• Nahoru Třídění otázek a problémů v rozhovoru
• Procvičte si úlohy na algoritmu řazení

3. Algoritmus rozděl a panuj

Rozděl a panuj Algoritmy sledují rekurzivní strategii řešení problémů tak, že je rozdělují na menší dílčí problémy, řeší tyto dílčí problémy a kombinují řešení za účelem získání konečného řešení.

kroky:

1. Rozdělit : Rozdělte problém na menší, nezávislé podproblémy.
2. Dobýt : Rekurzivně vyřešte každý dílčí problém.
3. Kombajn : Sloučením řešení dílčích problémů získáte konečné řešení.

Příklady:

• Sloučit řazení: Rozdělí pole na dvě poloviny, každou polovinu seřadí rekurzivně a seřazené poloviny sloučí.
• Rychlé řazení: Vybere prvek pivotu, rozdělí pole na dvě podpole na základě pivotu a rekurzivně seřadí každé podpole.
• Binární vyhledávání: Opakovaně rozdělí vyhledávací prostor na polovinu, dokud není nalezen cílový prvek nebo dokud není vyčerpán vyhledávací prostor.

Související články:

• Výukový program Rozděl a panuj
• Procvičte si úlohy na algoritmu rozděl a panuj

4. Chamtivé algoritmy

Jak název napovídá, tento algoritmus sestaví řešení jeden kus po druhém a vybere další kus, který poskytuje nejviditelnější a okamžitý přínos, tj. který je v danou chvíli nejoptimálnější volbou. Takže problémy, kdy volba lokálně optimálního také vede ke globálním řešením, jsou pro Greedyho nejvhodnější.

Některé důležité problémy chamtivých algoritmů jsou:

Související články:

• Výukový program Greedy Algorithm
• Procvičte si problémy na Greedyho algoritmu

5. Rekurze

Rekurze je programovací technika, kde funkce volá sama sebe v rámci své vlastní definice. Obvykle se používá k řešení problémů, které lze rozdělit na menší instance stejného problému. Například: Hanojské věže (TOH) , Faktorový výpočet a Fibonacciho sekvence atd.

Kroky :

• Základní pouzdro : Definujte podmínku, která zastaví rekurzivní volání a poskytne řešení.
• Rekurzivní případ : Definujte kroky pro rozdělení problému na menší instance a proveďte rekurzivní volání.
• Vrátit se : Vraťte řešení z rekurzivních volání a zkombinujte je, abyste vyřešili původní problém.

Pointa, která dělá rekurzi jedním z nejpoužívanějších algoritmů, je to, že tvoří základ pro mnoho dalších algoritmů, jako je např. Přechody stromů , Procházení grafů , Algoritmy rozděl a panuj a Algoritmy zpětného sledování .

Související témata:

• Výukový program rekurze
• Rekurzivní funkce
• Rekurze ocasu
• 50 hlavních problémů rekurzního algoritmu pro rozhovor
• Procvičte problémy na algoritmu rekurze

6. Algoritmus zpětného sledování

Jak již bylo zmíněno dříve, Zpětné sledování algoritmus je odvozen od algoritmu rekurze s možností vrátit se v případě selhání rekurzivního řešení, tj. v případě, že řešení selže, program se vrátí do okamžiku, kdy selhalo, a staví na jiném řešení. V podstatě tedy vyzkouší všechna možná řešení a najde to správné.

Některé důležité a nejběžnější problémy algoritmů zpětného sledování, které musíte vyřešit, než budete pokračovat, jsou:

Související článek:

• Backtracking Tutorial
• Procvičte si problémy na algoritmu Backtracking

7. Dynamické programování

Dynamické programování je metoda používaná v matematice a informatice k řešení složitých problémů jejich rozdělením na jednodušší dílčí problémy. Řešením každého dílčího problému pouze jednou a uložením výsledků se vyhnete nadbytečným výpočtům, což vede k efektivnějším řešením pro širokou škálu problémů.

jak číst soubor json

Klíčové koncepty:

• Optimální spodní konstrukce : Optimální řešení problému lze sestavit z optimálních řešení jeho dílčích problémů.
• Překrývající se dílčí problémy : Dílčí problémy se často opakují ve větším problému, což vede k nadbytečným výpočtům.
• Pamatování / Tabulování : Ukládání řešení dílčích problémů, aby se zabránilo přepočítávání.

Některé důležité a nejčastější problémy algoritmů dynamického programování, které musíte vyřešit, než budete pokračovat, jsou:

Související články:

• Tabulování vs memoizace
• Jak vyřešit problém dynamického programování?
• Výuka dynamického programování
• 50 hlavních problémů s kódováním dynamického programování pro rozhovory
• Procvičte si úlohy na algoritmu dynamického programování

8. Grafové algoritmy :

Grafové algoritmy v datových strukturách a algoritmech (DSA) je soubor technik a metod používaných k řešení problémů souvisejících s grafy, které jsou souborem uzlů a hran. Tyto algoritmy jsou navrženy k provádění různých operací s grafy, jako např hledání, procházení, hledání nejkratší cesty a určování konektivitu . Jsou nezbytné pro řešení široké škály problémů v reálném světě, včetně směrování sítě, analýzy sociálních sítí a alokace zdrojů.

Související témata:

• Výukový program pro grafy
• 50 nejčastějších problémů s kódováním grafů pro rozhovory
• Cvičný problém s grafovými algoritmy

9 . Hledání vzoru

Hledání vzorů je základní technika v DSA používaná k nalezení výskytů konkrétního vzoru v daném textu.

python nový řádek

Níže jsou uvedeny některé standardní algoritmy vyhledávání vzorů:

Související témata:

• Výukový program pro vyhledávání vzorů
• Cvičení Problém zapnut Hledání vzoru

10 . Matematické algoritmy

Matematické algoritmy jsou třídou algoritmů, které řeší problémy související s matematickými pojmy. Jsou široce používány v různých oblastech, včetně počítačové grafiky, numerické analýzy, optimalizace a kryptografie.

Související témata:

• Cvičný problém z matematického algoritmu

11. Geometrické algoritmy

Geometrické algoritmy jsou třídou algoritmů, které řeší problémy související s geometrií. Geometrické algoritmy jsou nezbytné pro řešení široké škály problémů v informatice, jako jsou:

Související témata:

• Cvičný problém z geometrických algoritmů

12. Bitové algoritmy

Bitové algoritmy jsou algoritmy, které pracují s jednotlivými bity čísel. Tyto algoritmy manipulují s binární reprezentací čísel a provádějí úkoly, jako je bitová manipulace, bitové logické operace (AND, OR, XOR), posouvání bitů , a nastavení nebo vymazání konkrétních bitů v rámci čísla. Běžně se používají bitové algoritmy nízkoúrovňové programování, kryptografie a optimalizační úlohy kde je vyžadována efektivní manipulace s jednotlivými bity.

Související témata:

• Výuka bitových algoritmů
• Cvičný problém na bitových algoritmech

13. Randomizované algoritmy

Randomizované algoritmy jsou algoritmy, které k řešení problémů používají náhodnost. K dosažení svých cílů využívají náhodné vstupy, což často vede k jednodušším nebo efektivnějším řešením.

Typy randomizovaných algoritmů:

• Las Vegas : Vždy vytváří správný výsledek, ale doba běhu je náhodná.
• Monte Carlo : Může způsobit nesprávný výsledek s malou pravděpodobností, ale doba běhu je obvykle rychlejší.

Důležité algoritmy, které používají algoritmy randomizace:

14. Větevný a vázaný algoritmus

The Branch and Bound Algorithm je metoda používaná v kombinatorických optimalizačních problémech k systematickému hledání nejlepšího řešení. Funguje to tak, že se problém rozdělí na menší podproblémy nebo větve a poté se určité větve vyloučí na základě mezí optimálního řešení. Tento proces pokračuje, dokud není nalezeno nejlepší řešení nebo dokud nejsou prozkoumány všechny větve.

Standardní problémy s větveným a vázaným algoritmem:

Související témata:

• Výukový program větveného a vázaného algoritmu

Přečtěte si o složitosti

V datových strukturách a algoritmech (DSA) je hlavním cílem řešit problémy efektivně a efektivně. Abychom určili efektivitu programu, podíváme se na dva typy složitosti:

1. Časová složitost : To nám říká, jak dlouho trvá spuštění našeho kódu.
2. Vesmírná složitost : To nám říká, kolik paměti používá náš kód.

Asymptotická notace :

K porovnání účinnosti algoritmů používáme asymptotickou notaci, matematický nástroj, který odhaduje čas na základě vstupní velikost bez spuštění kódu. Zaměřuje se na počet základních operací v programu.

Nejčastěji používaným zápisem pro analýzu kódu je Velký O zápis , poskytující horní limit doby běhu nebo využití paměti týkající se velikosti vstupu.

Související témata:

• Pochopení časové složitosti pomocí jednoduchých příkladů
• Časová složitost různých datových struktur
• Jak analyzovat smyčky pro analýzu složitosti algoritmů
• Cvičné otázky o analýze časové složitosti

Cvičení problémových cheatů:

Vybrané seznamy problémů z níže uvedených článků:

• Plán DSA od Sandeep Jain
• SDE SHEET – Kompletní průvodce přípravou SDE
• techcodeview.com Master Sheet – Seznam všech Cheat Sheetů