Diskuze: Jaká je časová komplexita tohoto rekurzivního kódu?

Petr Šťastný

Tvůrce

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

David Dostal

Tvůrce

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 n⁶ (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č

Nahoru Odpovědět

17.11.2017 22:49

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:17.11.2017 22:56

Podle tvyho popisu bych rekl typicky (a minimalne) N⁶, nejhorsi N⁸, 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 17.11.2017 22:57

Nahoru Odpovědět

17.11.2017 22:56

https://www.facebook.com/peasantsandcastles/

Petr Šťastný

Tvůrce

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)

N² - (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 17.11.2017 23:04

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.