FINÁLNÍ VÝPRODEJ KREDITŮ na ITnetwork je tady. Využij poslední šanci a získej až 80 % extra kreditů ZDARMA na náš interaktivní e-learning. Zjisti více:
NOVINKA: Kurz kybernetické bezpečnosti s akreditací MŠMT, nyní již od 0 Kč. Staň se žádaným profesionálem. Zjisti více:
Avatar
Petr Šťastný
Tvůrce
Avatar
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
 
Odpovědět
31.3.2018 13:21
Avatar
coells
Tvůrce
Avatar
Odpovídá na Petr Šťastný
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č
Řešení problému
 
Nahoru Odpovědět
31.3.2018 17:01
Avatar
Petr Šťastný
Tvůrce
Avatar
Odpovídá na coells
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.