Rekurzní a třídící algoritmy

představím v podstatě všechny třídící algoritmy rekurzivně,takže bychom asi měli mluvit o rekurzi. Rekurze je opravdu rozšiřující mysltechnika, jakmile se dostanete na kloub. Je to také základ pro to, co by se dalo nazvat „matematickou interpretací“ počítačového programování, takže pokud jste CSci major, budete se s tím muset dříve nebo později vyrovnat. Podívejme se tedy na některé jednoduché algoritmy, jak iterativně (pomocí smyček), tak rekurzivně.

nalezení faktoriálu

faktoriál n je definován jako součin \(n (n-1) (n-2) \ldots (2) (1)\), tj. produkt všech celých čísel až do A včetně n. Je snadné psátjako smyčku:

int factorial_iter(int n) { int r = 1; // Factorial of 0 is 1 for(int i = 1; i <= n; ++i) r *= i; return r;}

Chcete-li napsat tento, nebo jakýkoli jiný algoritmus, rekurzivně, musíme položit dvě otázky:

  • jaký je nejmenší případ, případ, kdy mohu dát odpověď hned? Tomu se říká „základní případ“. (Někdy může být více než jeden nejmenší případ, a to je v pořádku.)

  • pro cokoli, co není nejmenší případ, jak to rozložím, aby bylo menší? Tomu se říká rekurzivní případ.

pro faktoriál je základním případem to, co se stane, když \(n = 0\): loopdoesn ‚ t spustit vůbec, a 1 je vrácena. Můžeme tedy začít s rekurzivní verzí

int factorial_rec(int n) { if(n == 0) return 1; else ...}

abychom vytvořili rekurzivní případ, musíme se podívat na to, co se stane, když n > 0. Zejména, jak můžeme zlomit \(n!\ ) dolů do některých \(n‘ !, n‘ < n\)?Nejběžnějším případem je \(n ‚ = n-1\).

jedním ze způsobů, jak se na to podívat, je předpokládat, že již máme hodnotu \((n-1)!\ ), a chceme se dostat \(n!\) z toho. To znamená, že předpokládejme, žefactorial_rec(n - 1) bude fungovat a dá nám správnou odpověď; stačí z něj postavit faktoriál n. Jak to můžeme udělat?\(n! = n (n-1)!\). Takže píšeme náš rekurzivní případ takto:

int fact(int n) { if(n == 0) return 1; else return n * fact(n - 1);}

Pojďme si chvilku projít procesem výpočtu factorial_rec(3):

  • fact(3) = 3 * fact(2)

  • fact(2) = 2 * fact(1)

  • fact(1) = 1 * fact(0)

  • fact(0) = 1 a v tomto bodě se můžeme vrátit zpět a dát výsledek 3 * 2 * 1 * 1 = 6.

induktivní důkaz

jak ukážeme, že funkce dělá to, co má dělat? Mohli bychom to otestovat, spustit to tisíckrát nebo milionkrát a ověřit, že jeho výstup je to, co očekáváme ,ale to vyžaduje, abychom přišli s nezávislým způsobem, jak definovatco funkce dělá (např., jiný způsob výpočtu faktoriálu), který sám o sobě může být nesprávný, a navíc opakované testování může pouze poskytnout statistickou jistotu, že náš algoritmus je správný. Pokud chceme býtjistě, pak potřebujeme logický nebo matematický důkaz, že je správný. Forrecursivní funkce, to má často formu důkazu indukcí. Aninduktivní důkaz je druh matematického ekvivalentu rekurzivní funkce.Jako rekurzivní funkce má základní případ(y) (jeden základní případ, ve skutečnosti, pro každý základní případ ve funkci), a základní případy jsou obvykle snadné. Má také induktivní případ (jeden pro každý rekurzivní případ ve funkci), kteréjsou poněkud složitější,ale umožňují nám udělat něco jako rekurzi.

zvažte výše uvedený příklad. Chceme dokázat, že fact(n) = \(n!\ ), kdedefinice \(n! = n(n-1) (n-2)\ldots (2) (1), 0! = 1\).

důkaz indukcí na n (bez ohledu na proměnnou, na které provádíme rekurzi, říkáme, že děláme „důkaz indukcí“ na této proměnné):

  • základní případ, \(n = 0\) pak fact(0) = 1 =\(0!\ ) a jsme hotovi.

  • induktivní případ: V induktivním případě se snažíme dokázat, že fact(n) =\(n!\ ) ` pro některé \(n > 0\). Můžeme rozdělit levou a pravou stranu a vidět, že ve skutečnosti máme

    $ $ n \ cdot \mathtt{fact} (n-1) = n! = n (n-1) (n-2) \ldots (2)(1)$$

    dělením \(n\) dostaneme

    $$\mathtt{fact}(n-1) = (n-1)(n-2) \ldots (2)(1) = (n-1)!$ $

    jinými slovy, snížili jsme problém dokázat, že fact(n) = \(n!\ ) k problému prokázání, že fact(n-1) =\((n-1)!\). To se nezdá užitečné, ale stejně jako v rekurzivní funkci, kde můžeme volat samotnou funkci s menším argumentem, v induktivním důkazu můžeme znovu použít samotný důkaz jako předpoklad pro menší \(n\). Tento předpoklad nazýváme induktivní hypotézou a vypadá to takto:

    $$\text{Předpokládejme}\qquad \ mathttt{fakt} (n‘) = n‘! \qquad \ text{for all}\; n ‚< n$$

    pokud necháme \(n ‚ = n-1\), pak máme

    $$\text{Předpokládejme}\qquad\mathttt{fakt}(n-1) = (n-1)!$ $

    což je přesně to, co jsme potřebovali výše! Nahrazením výše uvedeného získáme

    $$(n-1)! = (n-1)!$ $

    a jsme hotovi.

stejně jako rekurze je srdcem induktivního důkazu akt uplatnění samotného důkazu jako předpokladu o „menších“ hodnotách (\(n ‚ < n\)). Technicky existují dva druhy induktivních důkazů:

  • „indukce přirozeného čísla“ nám umožňuje pouze předpoklad o \(n ‚ = n-1\). To znamená, že můžeme předpokládat pouze „vstup“, který je menší než originál.

  • „silná indukce“ nám umožňuje použít libovolný \(n ‚ < n\). Silnou indukci můžete použít kdekoli, kde můžete použít indukci přirozeného čísla, ale není to vždy nutné.

výpočet celočíselného exponentu

Pamatujete si, když jsme pracovali na runtime složitosti naší funkce „Optimalizováno“ \(O (\log n)\) pro nalezení \(b^n\)? Můžeme psát rekurzivní verzi, že stejně. Ještě jednou se musíme zeptat

  • jaký je základní případ? V tomto případě je to, když \(n = 0\). V tom případě \(b^0 = 1\), bez ohledu na to, co je f (existuje nějaká debata o \(0^0\)).

  • jaký je rekurzivní případ? Jak rozdělíme \(b^n\) na \(b^{n‘}\)? Zde si vezmeme frontu z naší dřívější implementace:

    $$b^n = (b^{n/2})^2 \ quad \ text{if } n \ text{ je sudý}$$
    $$b^n = b \ cdot B^{n-1} \ quad \ text{if } n \ text{ je lichý}$$

to nám dává následující definici:

float powi(float b, int n) { if(n == 0) return 1; else if(n % 2 == 0) { // Even float fp = powi(b, n / 2); return fp * fp; } else if(n % 2 == 1) // Odd return f * powi(b, n - 1);}

to má stejnou složitost jako verze založená na smyčce a je pravděpodobně jednodušší.

v tomto případě, pokud chceme dokázat, že \(\mathtt{powi} (b, n) = b^n\) budeme potřebovat silnou indukci, protože jeden z rekurzivních případů zmenší vstup něčím jiným než jen -1.

důkaz, že \(\mathtt{powi} (b, n) = b^n\) silnou indukcí na \(n\):

  • základní případ: \(n = 0\)

    pak při pohledu na program dostaneme \(\mathtt{powi} (n, 0) = 1 = b^0\) a jsme hotovi.

  • induktivní případ: \(n > 0\), dokázat \(\mathtt{powi} (b, n) = b^n\). Zde jsou vlastně dva induktivní případy, každý jeden pro dva rekurzivní případy ve funkci. Naše induktivní hypotéza (předpoklad) je

    $$ \ mathtt{powi} (b,n‘) = b^{n‘}\qquad \ text{pro všechny}\; n ‚ < n$$
    • případ 1, \(n\) je sudý. Poté nahrazením volání na powi jeho návratovou hodnotou máme

      $$\mathtt{powi}(b, n / 2)^2 = b^n$$ $$\mathtt{powi}(b, n / 2)^2 = (b^{n/2})^2$$

      vezmeme druhou odmocninu obou stran:

      $$\mathtt{powi} (b, n/2) = b^{n/2}$$

      v tomto bodě můžeme použít IH, s \(n ‚ = n / 2\), přičemž

      $$b^{n / 2} = b^{n/2}$$
    • Případ 2, \(n\) je lichý. Poté rozbalením powi získáme

      $$b \cdot \mathtt{powi}(b,n-1) = b \cdot B^{n-1}$$ $$\mathtt{powi}(b,n-1) = b^{n-1} (\text{ divide by } b)$$ $$B^{n-1} = b^{n-1}\qquad\text{by IH,} (n ‚ = n-1)$$

    a důkaz je kompletní

vzájemná rekurze

vzájemná rekurze je, když definujeme několik rekurzivních funkcí z hlediska ostatních. Zvažte například následující definici sudé a liché:

  • přirozené číslo n je sudé iff \(n-1\) je liché.

  • přirozené číslo n je liché iff \(n-1\) je sudé.

  • \(1\) je lichý, \(0\) je sudý. (To jsou naše základní případy.)

pak můžeme definovat dvě funkce (predikáty), které rekurzivně odkazují na sebe:

bool is_even(int n) { if(n == 0) return true; else if(n == 1) return false; else return is_odd(n - 1);}bool is_odd(int n) { if(n == 0) return false; else if(n == 1) return true; else return is_even(n - 1);}

pokud sledujeme zpracování určení is_even(4), uvidíme toskáče tam a zpět mezi is_even a is_odd.

binární vyhledávání

provedli jsme binární vyhledávání iterativně, ale můžeme to udělat i rekurzivně:

  • existují dva základní případy: když najdeme položku nebo když je vyhledávací prostor zmenšen na 0 (což znamená, že položka nebyla nalezena).

  • rekurzivní případ porovnává hodnotu cíle s hodnotou v aktuálním středu a poté zmenšuje velikost vyhledávacího prostoru (rekurzivním prohledáváním levé nebo pravé strany).

vypadá to jako

template<typename T>int binary_search(const vector<T>& data, int low = 0, int high = data.size()-1, const T& target) { if(low > high) return -1; int mid = low + (high - low) / 2; // Why did I do this? if(data.at(mid) == target) return mid; else if(data.at(mid) < target) // Search right return binary_search(data, mid+1, high, target); else if(data.at(mid) > target) // Search left return binary_search(data, low, mid-1, target);}

další příklady: počítání počtu kopií ve vektoru. Pro každou rekurzi ve vektorovém stylu musíme sledovat naše“ výchozí místo “ ve vektoru. Je to proto, že nemůžeme zmenšit samotný vektor, takže do něj musíme vložit značku ukazující, kde začínáme. Můžeme to udělat dvěma způsoby, s parametrem int start nebo pomocí iterátorů.

template<typename T>int count(vector<T> data, int start, T target) { if(start == data.size()) return 0; else return (data.at(start) == target) + count(data, start + 1, target);}

s iterátory:

template<typename T, typename It>int count(It start, It finish, T target) { if(start == finish) return 0; else return (*start == target) + count(start + 1, finish, target);}

iterátory jsou něco jako ukazatele.

třídící algoritmy

třídící algoritmus je funkce, která bere posloupnost položek a nějakým způsobem je permutuje tak, že jsou nějakým způsobem uspořádány.Obvykle chceme, aby se věci uspořádaly podle běžných srovnávacích operátorů, takže pokud a < b pak a přijde před b v konečné permutaci.Ještě pořád, musíme se ujistit, že máme pravdu:

  • je zřejmé, že během procesu nemůžeme ztratit žádné prvky.

  • v originále mohou být duplikáty, pokud ano, ve výstupu by měl být stejný počet duplikátů.

  • pro větší pohodlí umožňujeme třídění prázdné sekvence (která při třídění vede k další prázdné sekvenci)

s tříděním jsou spojeny některé pojmy, o kterých je důležité si uvědomit:

  • stabilita-pokud má vstupní sekvence prvek, který se porovnává jako rovný, ale který je odlišný (např. zaměstnanci se stejnými jmény, ale jinak odlišnými lidmi), vyvstává otázka, zda se ve výstupní sekvenci vyskytují ve stejném pořadí jako v originále. Např., pokud zaměstnanec „John Smith“ #123 přišel před „John Smith“ #234 v původním pořadí, pak říkáme, že druh je stabilní, pokud #123 je před #234 ve výsledku.

    stabilita je důležitá při třídění sekvence podle více kritérií. Například, pokud budeme třídit na základě křestního jména, pak na základě příjmení, nestabilní druh nám nedá výsledek, který chceme: položky křestního jména budou všechny smíšené.

  • adaptabilita-některé vstupní sekvence jsou již částečně (nebo úplně) seřazeny; adaptabilní algoritmus třídění poběží rychleji (z hlediska big-O) na částečně tříděných vstupech. Optimální runtime pro kompletně tříděný vstup je \(O (n)\), čas potřebný k ověření, že vstup je již seřazen.

  • in – Place-algoritmus třídění na místě je ten, který nepotřebuje žádné další místo (tj., je to Prostorová složitost je \(O(1)\)) třídit. Některé algoritmy nelze použít na místě, a musí sestrojit samostatnou výstupní sekvenci stejné velikosti jako vstup, zapsat výsledky do.

  • Online-některé datové sady jsou příliš velké, aby se vůbec vešly do paměti. Algoritmus online třídění je algoritmus, který vyžaduje, aby všechna jeho data byla přístupná (v paměti). Offline algoritmy třídění mohou třídit data, která jsou částečně v paměti, částečně na disku nebo jiném „pomalém“ úložišti, aniž by to ovlivnilo jejich časovou složitost.

řazení výběru

už jsme se podívali na třídění výběru, takže se na to podívejme znovu:

  • Chcete-li vybrat třídit seznam položek, nejprve najdeme nejmenší položku v celém seznamu a umístíme ji na začátek.

  • pak najdeme nejmenší položku ve všem po první položce a položíme ji na druhou.

  • pokračujte, dokud nezůstane nic netříděného.

výběr řazení efektivně rozděluje seznam do tříděné oblasti na začátku a netříděné oblasti na konci. Tříděná oblast roste, zatímcotříděný region se zmenšuje.

Selection sort není stabilní.

iterativně to vypadá takto:

template<typename T>void selection_sort(vector<T> data) { for(auto it = begin(data); it != end(data)-1; ++it) { // Find smallest auto smallest = it; for(auto jt = it+1; jt != end(data); ++jt) if(*jt < *smallest) smallest = jt; // Swap it into place swap(it, smallest); }}

pojďme to sledovat na malém příkladu, abychom získali pocit, jak to funguje.

jak můžeme rekurzivně implementovat? Místo toho, abychom procházeli kolem skutečnéhovector, prostě projdeme kolem iterátorů na začátek a konec vektoru. Proč to děláme, bude brzy zřejmé:

template<typename Iterator>void selection_sort(Iterator first, Iterator last) { ...}

pojďme analyzovat rekurzi:

  • základní případ je, když last == first + 1. To znamená, že existuje pouze 1 prvek a seznam 1 prvků je vždy seřazen.

  • rekurzivní případ je, když last - first > 1. V takovém případě ji rekurzivně rozdělíme

    • a najdeme minimum oblasti a umístíme ji na začátek.
    • rekurzivně selection-třídění first+1 přes last (protože prvek na first je nyní na správném místě).
template<typename Iterator>void selection_sort(Iterator first, Iterator last) { if(last - first == 1) return; // 1 element, nothing to sort else { // Find minimum Iterator smallest = first; for(Iterator it = first; it != last; ++it) if(*it < *smallest) smallest = it; // Swap into place swap(*smallest, *first); // Recursively sort the remainder selection_sort(first + 1, last); }}

nakreslíme pro to rekurzní strom. Nebudeme sledovat smyčku, budemejen předpokládáme (prozatím), že funguje správně.

DIAGRAM

analýza algoritmu třídění

kromě analýzy obecného nejlepšího / nejhoršího běhu big-O algoritmu je běžné také analyzovat dvě další runtime funkce:

  • počet srovnání mezi prvky. To počítá pouze srovnání mezi tříděnými objekty, nikoli srovnání (např.) proměnné čítače smyček.

  • počet swapů mezi prvky.

analýza počtu srovnání a swapů je užitečná, protože tyto operace leží v srdci jakéhokoli algoritmu třídění: nemůžeme vědět, zdaprvky jsou mimo provoz, dokud je neporovnáme (a pokud jsou prvky složité, jejich porovnání může trvat netriviální množství času), a nemůžemedát je ve správném pořadí, aniž bychom je pohybovali – tj. vyměňovat je –

Bubble sort

Bubble sort je třídící algoritmus, který není vhodný pro rekurzivní implementaci. Cílem je porovnat sousední prvky ve vstupu (např., a a a) a vyměňte je, pokud jsou mimo provoz. Začínáme na začátku vstupu a procházíme jím a vyměníme si cestudo konce. Po jednom takovém průchodu bude největší prvek „bublat“ až do posledního prvku pole. Takže můžeme udělat další průchod, ale tentokrát přeskočíme poslední prvek. Zatímco Selection sort dělal menší a menší průchody počínaje zepředu, bubble sort dělá menší a menší průchody od konce.

třídění bublin je stabilní.

implementace vypadá asi takto:

template<typename T>void bubble_sort(vector<T>& data) { for(int j = 1; j < data.size(); ++j) for(int i = 0; i < data.size() - j; ++i) if(data.at(i) > data.at(i + 1)) swap(data.at(i), data.at(i + 1));}

při implementaci je tato funkce řádově \(O (n^2)\) v nejlepších i nejhorších případech; vnořená smyčka se stejnou „trojúhelníkovou“ strukturou, kterou jsme viděli dříve.Můžeme skutečně implementovat jednoduchou optimalizaci: ve vnitřní smyčce, pokud neprovádíme žádné swapy, je vstup tříděn a můžeme zastavit. Pokud to zkontrolujeme, může nám to umožnit předčasný odchod.

template<typename T>void bubble_sort(vector<T>& data) { for(int j = 1; j < data.size(); ++j) { bool sorted = true; for(int i = 0; i < data.size() - j; ++i) if(data.at(i) > data.at(i + 1)) { swap(data.at(i), data.at(i + 1)); sorted = false; } if(sorted) return; }}

jaké jsou nejlepší a nejhorší případy?

  • nejlepší případ je, když je vstup již seřazen. V tomto případě provedeme jeden průchod vektorem (abychom zkontrolovali, zda je tříděn), ale nic nevyměníme a pak se vrátíme. Takže nejlepší účinnost běhu je \(O (n)\).

  • nejhorším případem je pole, které je seřazeno sestupně. Každý prvek bude muset „bublat“ celou vzdálenost na své správné místo, takže nikdy neopustíme dříve (kvůli sorted) a podmínka ve příkazu if bude pokaždé pravdivá, takže provedeme tolik swapů, kolik je třeba. Pokud vypočítáme součet, dostaneme

    $$ \ sum_{j = 1}^n (n – j) = n – \sum_{j = 1}^n j$$

    kde druhá částka expanduje na \(\frac{n (n+1)}{2}\), dává nám pořadí \(O (n)\).

správnost třídění bublin

pokud chceme dokázat správnost třídění bublin, jako obvykle, to vše přijde na výběr správného invariantu (y). Zde je užitečné, pokud máme dvě, jednu smyčku:

template<typename T>void bubble_sort(vector<T>& data) { for(int j = 1; j < data.size(); ++j) { bool sorted = true; for(int i = 0; i < data.size() - j; ++i) if(data.at(i) > data.at(i + 1)) { swap(data.at(i), data.at(i + 1)); // INVARIANT: every element in data to data is *smaller* // than data. sorted = false; } // INVARIANT: every element of data to data is smaller // than data, and every element of data to // data is larger than data. (That is, // data is in the right place.) if(sorted) return; }}

řazení vložení

Předpokládejme, že vstup rozdělíme do dvou „sekcí“, tříděných a netříděných. Tříděná část je zpočátku prázdná. Pro každý prvek v netříděné sekci jej vložíme do tříděné sekce, v její správné, tříděné poloze. Protože se jedná o pole / vektor, vložení prvku vyžaduje posunutí všech prvků o jeden krok nahoru. I když můžeme vytvořit verzi, která funguje“na místě“, na jediném poli (protože když tříděná oblast roste o 1, nesortovaná oblast se zmenší o 1, takže celková velikost je vždy n), bude to jednodušší pochopit, pokud ji napíšeme jako funkci, která přesune prvky z anunsortovaného vektoru do tříděného vektoru, který je pak vrácen.

řazení vložení je stabilní.

template<typename T>vector<T> insertion_sort(vector<T>& data) { vector<T> sorted; for(int i = 0; i < data.size(); ++i) { T& item = data.at(i); // Find the proper place for item in sorted int pos = sorted.size(); // Defaults to the end for(int j = 0; j < sorted.size(); ++j) if(sorted.at(j) >= item) { pos = j; break; } // Insert the item at pos, by shifting everything forward // (Increases the size of sorted by 1) sorted.insert(sorted.begin() + pos, item); }}

jaké jsou nejlepší a nejhorší případy pro tento algoritmus? Je to trochu ošidné přijít na to, protože složitost insert je úměrná počtu přesunutých prvků (tj. sorted.size() - pos). Takže zatímco hledání pozice může skončit brzy (i v první iteraci), je to špatné pro vložku, protože to znamená, že pos bude malý, a proto je čas insert spíše špatný. Na druhou stranu, pokud vnitřní smyčka běží až do konce (pos = sorted.size()), pak insert účinně nenadělá nic jiného než push_back.

ve skutečnosti se vnitřní smyčka a insert vždy vyrovnávají, takže celkový počet mezi nimi je sorted.size(). A sorted.size() se zvyšuje o jednukaždý přes vnější smyčku, takže opět máme naši „trojúhelníkovou“ smyčku.

můžeme napsat rekurzivní verzi pomocí obslužných funkcí:

  • insert umístí prvek na správné místo v tříděné oblasti, opět posunutím všeho nahoru.

s těmito dvěma na místě se rekurzivní implementace stává

template<typename Iterator>void insertion_sort(Iterator start, Iterator unsorted, Iterator finish) { if(start == finish - 1) return; // One element else { // Insert first unsorted element into sorted region insert(start, unsorted, *unsorted); // Recursively sort the remainder of the unsorted region. insertion_sort(start, unsorted+1, finish); }}

Napsat komentář

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