Leela Krišna
Leela Krishna

následovat

1. dubna 2019 * 4 min čtení

v programovacím jazyce swift …

část -1:

proč datové struktury?

při vytváření moderních aplikací je často přehlížena velká část teorie vlastní algoritmům. Pro řešení, která spotřebovávají relativně malé množství dat, nemusí být rozhodnutí o konkrétních technikách nebo návrhových vzorcích důležitá, protože věci fungují. Jak však publikum roste, tak i data. Hodně z toho, co velké technologické společnosti úspěšné je dědic schopnost interpretovat obrovské množství dat. Smysl dat umožňuje uživatelům připojit se, sdílet, dokončit transakce, a rozhodovat se.

→ Datové Struktury :

  • základní(elementární) datové struktury

zásobník, fronta, třídící algoritmy

  • stromy

stromy & binární stromy, binární vyhledávání, halda, třídění haldy, prioritní fronta

  • grafy

grafy, seznam sousedství, Dijkstrův algoritmus, Prim algoritmus

→ big o notace :

asymptotická analýza je proces popisu účinnosti algoritmů a je běžně vyjádřen v běžném formátu známém jako Big O notace.

  • Časová Složitost :

množství času na dokončení algoritmu(funkce), jak jeho vstupní velikost (n) roste.

  • složitost prostoru:

množství paměti (prostoru) potřebné pro spuštění algoritmu (funkce).

obojí lze vyjádřit velkým O notací.

  • nejčastější časové složitosti :

→ konstantní čas (O(1)) :-

algoritmus s konstantním časem má stejnou dobu běhu bez ohledu na jeho vstup. Velký O zápis pro toto je O (1).

→ lineární čas (O (n)) :-

algoritmus lineárního času je jeho rychlost závislá na jeho vstupní velikosti. Jinými slovy se stává méně efektivní, jak jeho vstupní velikost(n) roste.

→ kvadratický čas (O (n2)) :-

jedná se o algoritmus, který vyžaduje čas na úměrný čtverci vstupní velikosti. Rychle se vymkne kontrole, jak se jeho velikost vstupu zvyšuje.

→ logaritmický čas (o(log n)) :-

běžným algoritmem s časovou složitostí O (log n) je binární vyhledávání, jehož rekurzivní vztah je T (n / 2) + O (1), tj. na každé následující úrovni stromu rozdělíte problém na polovinu a provedete konstantní množství další práce.

→ Kvazilineární čas (O (n log n)) :-

o algoritmu se říká, že běží v kvazilineárním čase (označovaném také jako log-lineární čas), pokud T (n) = O(n log^k n) pro nějakou kladnou konstantu k; linearitmický čas je případ k = 1.

příklad :

Struktura dat je systematický způsob organizace dat, aby bylo možné je efektivně využívat. Následující pojmy jsou základem datové struktury.

  • rozhraní-každá datová struktura má rozhraní. Rozhraní představuje sadu operací, které datová struktura podporuje. Rozhraní poskytuje pouze seznam podporovaných operací, Typ parametrů, které mohou přijmout a vrátit typ těchto operací.
  • implementace-implementace poskytuje interní reprezentaci datové struktury. Implementace také poskytuje definici algoritmů používaných při operacích datové struktury.

→ charakteristika datové struktury :

  • správnost-implementace datové struktury by měla správně implementovat své rozhraní.
  • časová složitost-doba běhu nebo doba provádění operací datové struktury musí být co nejmenší.
  • složitost prostoru − využití paměti operace datové struktury by mělo být co nejmenší.

→ potřeba datové struktury:

vzhledem k tomu, že aplikace jsou stále složité a bohaté na data, existují tři běžné problémy, kterým aplikace čelí nyní.

  1. vyhledávání dat-zvažte soupis 1 milionu (106) položek obchodu. V případě, že aplikace je hledat položku, musí hledat položku v 1 milion(106) položek pokaždé, když zpomaluje vyhledávání. Jak data rostou, vyhledávání bude pomalejší.
  2. rychlost procesoru – rychlost procesoru, i když je velmi vysoká, klesá omezená, pokud data rostou na miliardy záznamů.
  3. více požadavků – protože tisíce uživatelů mohou vyhledávat data současně na webovém serveru, i rychlý server selže při vyhledávání dat.

k vyřešení výše uvedených problémů dochází k záchraně datových struktur. Data mohou být uspořádána do datové struktury takovým způsobem, že nemusí být vyžadováno prohledávání všech položek a požadovaná data lze prohledávat téměř okamžitě.

→ podívejme se na obal zásobníku v swift:

vytvoříme obal kolem pole swift, kde pole používáme jako strukturu úložiště. Pole dávají konstantní čas (o (1)) Vložení a odstranění, když jsou prováděny od konce pole.

je to FIFO → první v prvních datech.

příklady v systému iOS : Uinavigation Stack, vrátit funkce, atd.

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna.