POZOR, prodej kreditů už v neděli končí! S kódem NAPOSLEDY90 teď navíc získáš 90 % extra kreditů ZDARMA. 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ý:17.11.2017 22:04

Ahoj, mám jeden kód, pro který potřebuju zjistit časovou komplexitu. Díval jsem se na počítání časové komplexity a došel jsem k názoru, že tohle nespočítám, už to zkouším poměrně dlouho a pořád nevím. Jak spočítám algoritmus, když se (někdy) rekurzivně opakuje? A jaký je výsledek? Díky :)

Zkrácený kód a zjednodušený kód, nechal jsem jenom cykly a rekurze. Detaily jsou vysvětlené komenáři:

public static void Main(string[] args)
{
    object reseni;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            for(int a = i; a < N; a++){
                for(int b = j; b < N; b++){
                    object noveReseni = RekurzivniMetoda();
                    if(noveReseni.JeLepsiNez(reseni))
                        reseni = noveReseni;
                }
            }
        }
    }
}

// Tato metoda prijima 2rozmerne pole, ktere zpracovava.
public static object RekurzivniMetoda(/* ... */){
    object reseni;

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            for(int a = -1; a <= 1; a++){
                for(int b = -1; b <= 1; b++){
                    // Zde se mi budto hnedka podari najit reseni, nebo (kdyz ne), spustim rekurzivne tu samou metodu.
                    // Jsou tu dalsi omezeni, takze rekurzivne hledam v malem poctu pripadu, rozhodne to neni tak, ze rekurzi volam pokazde, kdyz nenajdu reseni.
                    // V kazdem poli je minimalne 1 reseni, reseni je tedy 100% nalezeno po tom, co projedu N^2 prvku
                    // Pri kazdem probehnuti teto metody zpracuji v prumeru asi 10 prvku
                    if(nalezenoReseni){
                        object noveReseni = new object(); /* ... */
                        if(noveReseni.JeLepsiNez(reseni)){
                            reseni = noveReseni;
                        }
                    }else if(/* vetsinou rekurze neprobehne */){
                       RekurzivniMetoda(/* ... */);
                    }
                }
            }
        }
    }

    return reseni;
}

Vím, že je může být nepřehledné a zmatené, je to poněkud zdlouhavé řešení problému, který řeším, ale lepší způsob mě zatím nenapadl. Kdybyste potřebovali něco osvětlit, určitě napište, rád vše vysvětlím. Celkový kód bych sem raději nedával, už jenom z toho důvodu, že to je opravdu zdlouhavé (třeba zkoušení toho, jestli jsem už našel řešení, nebo třeba když se rozhoduji, jestli se má spustit rekurze). Byl bych rád, kdyby se někomu podařilo časová složitost odhadnout bez konkrétního kódu.

Díky, Petr

 
Odpovědět
17.11.2017 22:04
Avatar
David Dostal
Tvůrce
Avatar
David Dostal:17.11.2017 22:49

Wow, s takovým kódem jsem se ještě nesetkal :-)
Nejsem na to odborník, tak to ber s rezervou:
V nejlepším případě (řešení se najde a neproběhne rekurze) bude časová složitost n6 (6 zanořených cyklů o délce n, zbytek je zanedbatelný). Průměrnou složitost těžko posoudit, záleží na podmínce pro nalezení řešení. Záleží na podmínce pro nalezené řešení a zda je výsledek předpověditelný, v nejhorším případě teoreticky může běžet kód do nekonečna (tedy pokud se nezaplní stack v případě že n je tak malé, že to stihne).

V jakých řádech se N obvykle pohybuje? Zkoušel jsi ten kód spouštět?

Pokud dělá rekurze problém se zjištěním časové složitosti, můžeš si to přepsat do podoby bez ní (místo rekurzivního předávání argumentů budeš hodnoty ukládat do nějaké proměnné).

Akceptované řešení
+20 Zkušeností
+2,50 Kč
Řešení problému
 
Nahoru Odpovědět
17.11.2017 22:49
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Luboš Běhounek Satik:17.11.2017 22:56

Podle tvyho popisu bych rekl typicky (a minimalne) N6, nejhorsi N8, jestli jsem dobre pochopil tvuj popis - ze rekurze se muze v rekurzivni metode vnorovat maximalne o jednu uroven, protoze tam se uz vzdycky najde reseni.

Editováno
Nahoru Odpovědět
17.11.2017 22:56
https://www.facebook.com/peasantsandcastles/
Avatar
Petr Šťastný
Tvůrce
Avatar
Petr Šťastný:17.11.2017 23:02

Rekurze se muze vyskytnout az (predpokladam, ze pole ma vetsi velikost, u pole 1x1 to rekurzivne nepujde samozrejme vubec)

N2 - (pocet vnoreni 2. metody * 10) v nejhorsim pripade, v prumernem se spusti dle zadani asi pro N=10, 3krat. Asi si to prepisu mimo rekurzi, jak rikal David Dostal, asi to pak pujde nejak lepe urcit.

Dekuji vsem :)

Editováno
 
Nahoru Odpovědět
17.11.2017 23:02
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 4 zpráv z 4.