Rekurze je základní koncept v informatice a matematice, který umožňuje funkcím volat samy sebe, což umožňuje řešení složitých problémů pomocí iteračních kroků. Jedna vizuální reprezentace běžně používaná k pochopení a analýze provádění rekurzivních funkcí je strom rekurze. V tomto článku prozkoumáme teorii za rekurzivními stromy, jejich strukturu a jejich význam pro pochopení rekurzivních algoritmů.
Co je to strom rekurze?
Strom rekurze je grafické znázornění, které ilustruje tok provádění rekurzivní funkce. Poskytuje vizuální rozpis rekurzivních volání a ukazuje postup algoritmu, jak se větví a nakonec dosáhne základního případu. Stromová struktura pomáhá při analýze časové složitosti a pochopení rekurzivního procesu.
Stromová struktura
Každý uzel ve stromu rekurze představuje konkrétní rekurzivní volání. Počáteční volání je znázorněno nahoře, další volání se rozvětvují pod ní. Strom roste směrem dolů a vytváří hierarchickou strukturu. Faktor větvení každého uzlu závisí na počtu rekurzivních volání provedených v rámci funkce. Hloubka stromu navíc odpovídá počtu rekurzivních volání před dosažením základního případu.
Základní pouzdro
Základní případ slouží jako ukončovací podmínka pro rekurzivní funkci. Definuje bod, ve kterém se rekurze zastaví a funkce začne vracet hodnoty. Ve stromu rekurze jsou uzly reprezentující základní případ obvykle zobrazeny jako listové uzly, protože nevedou k dalším rekurzivním voláním.
počítačové sítě
Rekurzivní volání
Podřízené uzly ve stromu rekurze představují rekurzivní volání provedená v rámci funkce. Každý podřízený uzel odpovídá samostatnému rekurzivnímu volání, což vede k vytvoření nových dílčích problémů. Hodnoty nebo parametry předávané těmto rekurzivním voláním se mohou lišit, což vede k odchylkám v charakteristikách dílčích problémů.
Průběh provádění:
Procházení stromu rekurze poskytuje pohled na tok provádění rekurzivní funkce. Počínaje počátečním voláním v kořenovém uzlu sledujeme větve, abychom dosáhli dalších volání, dokud nenarazíme na základní případ. Po dosažení základních případů se rekurzivní volání začnou vracet a jejich příslušné uzly ve stromu jsou označeny vrácenými hodnotami. Přechod pokračuje, dokud není projetý celý strom.
Analýza časové složitosti
Rekurzivní stromy pomáhají při analýze časové složitosti rekurzivních algoritmů. Zkoumáním struktury stromu můžeme určit počet uskutečněných rekurzivních volání a práci vykonanou na každé úrovni. Tato analýza pomáhá porozumět celkové efektivitě algoritmu a identifikovat případné neefektivnosti nebo příležitosti k optimalizaci.
Úvod
- Představte si program, který určuje faktoriál čísla. Tato funkce bere jako vstup číslo N a jako výsledek vrací faktoriál N. Pseudokód této funkce bude připomínat,
// find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ - Rekurze je příkladem funkce, která byla zmíněna dříve. Vyvoláváme funkci k určení faktoriálu čísla. Poté, při nižší hodnotě stejného čísla, tato funkce volá sama sebe. Toto pokračuje, dokud nedosáhneme základního případu, ve kterém již nejsou žádná volání funkcí.
- Rekurze je technika pro řešení komplikovaných problémů, kdy výsledek závisí na výsledcích menších případů stejného problému.
- Pokud přemýšlíme o funkcích, říká se, že funkce je rekurzivní, pokud sama sebe volá, dokud nedosáhne základního případu.
- Každá rekurzivní funkce má dvě primární složky: základní případ a rekurzivní krok. Jakmile dosáhneme základního případu, přestaneme přecházet do rekurzivní fáze. Aby se zabránilo nekonečné rekurzi, musí být základní případy správně definovány a jsou klíčové. Definice nekonečné rekurze je rekurze, která nikdy nedosáhne základního případu. Pokud program nikdy nedosáhne základního případu, přetečení zásobníku bude pokračovat.
Typy rekurze
Obecně řečeno, existují dvě různé formy rekurze:
- Lineární rekurze
- Rekurze stromu
- Lineární rekurze
Lineární rekurze
- Funkce, která se při každém provedení zavolá pouze jednou, se nazývá lineárně rekurzivní. Pěknou ilustrací lineární rekurze je faktoriál. Název 'lineární rekurze' odkazuje na skutečnost, že provedení lineárně rekurzivní funkce trvá lineárně dlouho.
- Podívejte se na níže uvedený pseudokód:
function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } - Pokud se podíváme na funkci doSomething(n), přijme parametr s názvem n a provede nějaké výpočty, než zavolá stejnou proceduru ještě jednou, ale s nižšími hodnotami.
- Když je zavolána metoda doSomething() s hodnotou argumentu n, řekněme, že T(n) představuje celkovou dobu potřebnou k dokončení výpočtu. K tomu můžeme také formulovat rekurentní vztah, T(n) = T(n-1) + K. K zde slouží jako konstanta. Konstanta K je zahrnuta, protože funkci trvá určitou dobu, než přidělí nebo zruší přidělení paměti proměnné nebo provede matematickou operaci. K definování času používáme K, protože je tak minutový a bezvýznamný.
- Časovou složitost tohoto rekurzivního programu lze jednoduše vypočítat, protože v nejhorším scénáři je metoda doSomething() volána nkrát. Formálně řečeno, časová složitost funkce je O(N).
Rekurze stromu
- Když provedete rekurzivní volání v rekurzivním případě více než jednou, nazývá se to stromová rekurze. Účinnou ilustrací stromové rekurze je Fibonacciho sekvence. Stromové rekurzivní funkce pracují v exponenciálním čase; nejsou lineární ve své časové složitosti.
- Podívejte se na níže uvedený pseudokód,
function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } - Jediný rozdíl mezi tímto kódem a předchozím je v tom, že tento provede ještě jedno volání stejné funkce s nižší hodnotou n.
- Položme T(n) = T(n-1) + T(n-2) + k jako rekurenci opakování pro tuto funkci. K slouží ještě jednou jako konstanta.
- Když se provede více než jedno volání stejné funkce s menšími hodnotami, tento druh rekurze se nazývá stromová rekurze. Zajímavým aspektem je nyní: jak časově náročná je tato funkce?
- Odhadněte stejnou funkci na základě níže uvedeného stromu rekurze.
- Možná vás napadne, že je náročné odhadnout časovou složitost přímým pohledem na rekurzivní funkci, zvláště když se jedná o stromovou rekurzi. Metoda stromu rekurze je jednou z několika technik pro výpočet časové složitosti takových funkcí. Pojďme to prozkoumat podrobněji.
Co je metoda stromu rekurze?
- Rekurentní vztahy jako T(N) = T(N/2) + N nebo dva, které jsme probrali dříve v sekci o druzích rekurze, jsou řešeny pomocí přístupu stromu rekurze. Tyto recidivující vztahy často používají k řešení problémů strategii rozděl a panuj.
- Integrace odpovědí na menší dílčí problémy, které vzniknou, když je větší problém rozdělen na menší dílčí problémy, nějakou dobu trvá.
- Relace opakování je například T(N) = 2 * T(N/2) + O(N) pro řazení Sloučit. Čas potřebný ke spojení odpovědí na dva dílčí problémy s kombinovanou velikostí T(N/2) je O(N), což platí i na úrovni implementace.
- Například, protože relace opakování pro binární vyhledávání je T(N) = T(N/2) + 1, víme, že každá iterace binárního vyhledávání má za následek prohledávání, které je zkráceno na polovinu. Jakmile je výsledek určen, opustíme funkci. Vztah opakování byl přidán +1, protože se jedná o operaci s konstantním časem.
- Je třeba vzít v úvahu vztah opakování T(n) = 2T(n/2) + Kn. Kn označuje množství času potřebného ke spojení odpovědí na n/2-rozměrné dílčí problémy.
- Pojďme si znázornit strom rekurze pro výše zmíněný rekurzivní vztah.
Ze studia výše uvedeného stromu rekurze můžeme vyvodit několik závěrů, včetně
1. Pro určení hodnoty uzlu záleží pouze na velikosti problému na každé úrovni. Velikost problému je n na úrovni 0, n/2 na úrovni 1, n/2 na úrovni 2 a tak dále.
2. Obecně definujeme výšku stromu jako log (n), kde n je velikost problému a výška tohoto stromu rekurze je rovna počtu úrovní ve stromu. To je pravda, protože, jak jsme právě zjistili, strategii rozděl a panuj používají rekurentní vztahy k řešení problémů a dostat se z velikosti problému n na velikost problému 1 jednoduše vyžaduje provedení log (n) kroků.
- Uvažujme například hodnotu N = 16. Pokud je nám dovoleno dělit N v každém kroku 2, kolik kroků je potřeba, abychom dostali N = 1? Vzhledem k tomu, že v každém kroku dělíme dvěma, správná odpověď je 4, což je hodnota log(16) základ 2.
log(16) základ 2
log(2^4) základ 2
4 * log(2) základ 2, protože log(a) základ a = 1
takže 4 * log(2) základ 2 = 4
python seřazená n-tice
3. Na každé úrovni je druhý člen v opakování považován za kořen.
Přestože se v názvu této strategie objevuje slovo 'strom', nemusíte být odborníkem na stromy, abyste to pochopili.
Jak používat strom rekurze k řešení vztahů s opakováním?
Cena dílčího problému v technice rekurzního stromu je množství času potřebného k vyřešení dílčího problému. Pokud si tedy všimnete fráze „náklady“ spojené se stromem rekurze, vztahuje se jednoduše k množství času potřebného k vyřešení určitého dílčího problému.
Pojďme si všechny tyto kroky vysvětlit na několika příkladech.
příkaz java switch
Příklad
Zvažte vztah opakování,
T(n) = 2T(n/2) + K
Řešení
Daný vztah opakování vykazuje následující vlastnosti,
Problém velikosti n je rozdělen na dva dílčí problémy, každý o velikosti n/2. Náklady na kombinaci řešení těchto dílčích problémů jsou K.
Každý problém velikosti n/2 je rozdělen do dvou podproblémů, každý velikosti n/4 a tak dále.
Na poslední úrovni se velikost dílčího problému sníží na 1. Jinými slovy, konečně jsme narazili na základní případ.
Podívejme se na kroky k vyřešení tohoto vztahu opakování,
Krok 1: Nakreslete strom rekurze
int na řetězec v jazyce Java
Krok 2: Vypočítejte výšku stromu
Protože víme, že když číslo dělíme nepřetržitě 2, nastane čas, kdy se toto číslo zmenší na 1. Stejně jako u problému velikosti N, předpokládejme, že po K děleních 2 se N rovná 1, což znamená, ( n/2^k) = 1
Zde n / 2^k je velikost problému na poslední úrovni a je vždy rovna 1.
Nyní můžeme snadno vypočítat hodnotu k z výše uvedeného výrazu tím, že vezmeme log() na obě strany. Níže je jasnější odvození,
n = 2^k
- log(n) = log(2^k)
- log(n) = k * log(2)
- k = log(n) / log(2)
- k = log(n) základ 2
Výška stromu je tedy log (n) základna 2.
Krok 3: Vypočítejte náklady na každé úrovni
- Náklady na úrovni 0 = K, dva dílčí problémy jsou sloučeny.
- Náklady na úrovni 1 = K + K = 2*K, dva dílčí problémy jsou sloučeny dvakrát.
- Náklady na úrovni 2 = K + K + K + K = 4*K, dva dílčí problémy jsou čtyřikrát sloučeny. a tak dále....
Krok 4: Vypočítejte počet uzlů na každé úrovni
Nejprve určíme počet uzlů v poslední úrovni. Ze stromu rekurze to můžeme odvodit
- Úroveň 0 má 1 (2^0) uzel
- Úroveň 1 má 2 (2^1) uzly
- Úroveň 2 má 4 (2^2) uzly
- Úroveň 3 má 8 (2^3) uzlů
Úroveň log(n) by tedy měla mít 2^(log(n)) uzlů, tj. n uzlů.
java získat aktuální čas
Krok 5: Sečtěte cenu všech úrovní
- Celkové náklady lze zapsat jako,
- Celkové náklady = náklady na všechny úrovně kromě poslední úrovně + náklady na poslední úroveň
- Celková cena = cena za úroveň-0 + cena za úroveň-1 + cena za úroveň-2 +.... + cena za úroveň-log(n) + cena za poslední úroveň
Náklady na poslední úroveň se počítají samostatně, protože se jedná o základní případ a na poslední úrovni se neprovádí žádné slučování, takže náklady na vyřešení jednoho problému na této úrovni jsou určitou konstantní hodnotou. Vezměme to jako O (1).
Dejme hodnoty do vzorců,
- T(n) = K + 2*K + 4*K + .... + log(n)` krát + `O(1) * n
- T(n) = K(1 + 2 + 4 + .... + log(n) krát)` + `O(n)
- T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) krát + O(n)
Pokud se pozorně podíváte na výše uvedený výraz, tvoří geometrickou posloupnost (a, ar, ar^2, ar^3 ...... nekonečný čas). Součet GP je dán vztahem S(N) = a / (r - 1). Zde je první člen a r je společný poměr.