Diskuze: Složitost rekurzivního algoritmu

Aktivity

Petr Šťastný

Tvůrce

Petr Šťastný:31.3.2018 13:21

Ahoj, potřebuji pomoct s určením časové složitosti jednoho algoritmu.

Algoritmus (značený H) volá (2^N)-1krát algoritmus EM.

Algoritmus EM má dvě větve: Buďto má složitost 1, nebo má složitost 2H(x)+1, kde x <= N, čímž volá zpátky algoritmus H.

Jak se v tomhle případě určuje časová složitost? Mám předpokládat, že se algoritmus EM bude větvit 50:50, tedy že algoritmus H zavolá v polovině případů? A co x? Mám předpokládat, že bude vždy N/2?

Díky

Editováno 31.3.2018 13:22

Odpovědět

31.3.2018 13:21

coells

Tvůrce

coells:31.3.2018 17:01

Protože nemáš rozdělení pravděpodobnosti, tak nemůžeš předpokládat nic, dokud distribuci nenajdeš, ale hádám, že statistiku jsi ještě neměl, tak je lepší ji do toho neplést.

Navíc pokud bys dělil případy EM s uniformní pravděpodobností, algoritmus by nemohl skončit, což plyne z limity exponenciální vůči lineární funkci.

Podle zadání máš deterministický algoritmus zadaný dvěma rekurentními funkcemi, takže si vyjádři H(n) jako funkci EM(n). Potom rozděl volání EM na dvě možnosti, kdy n-krát voláš 2H(n)+1 a zbytek času voláš konstatní funkci. Dosadíš za EM(n) do rovnice a dostaneš jednoduchý vztah, ze kterého vyjádříš H(n) a máš výsledek.

Jakkoliv se to může zdát abstraktní, jakmile vztahy mezi funkcemi převedeš do rovnic, všechno se zjednoduší.

Akceptované řešení
+20 Zkušeností
+2,50 Kč

Nahoru Odpovědět

31.3.2018 17:01

Petr Šťastný

Tvůrce

Petr Šťastný:31.3.2018 17:48

Díky

Nahoru Odpovědět

31.3.2018 17:48

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 3 zpráv z 3.