Udregning af køretid på rekursive kald

Du nævner ingen sprog, så her er lidt seudo:

startTid = nu;
kør rekursivt kald;
tid = nu - startTid;

"tid" er så tiden det rekursive kald tog.

Hvad mener du? Sådan målt i reel tid, eller en matematisk udregnet tidskompleksitet?

Hvis reel tid, sætter du vel bare en timer i dit program med evt. mellemtider i hver rekursion.

Hvis du vil udregne tidskompleksitet ( f.eks. T(n)= O(n*log n ) ), så kræver det en del matematisk indsigt.
Generelt skal du benytte "divide and conquer"-filosofien.
Der er flere forskellige metoder til at finde Tidskompleksiteten for en rekursiv relatition. Een går ud på at "gætte" nogle kompleksiteter og så teste om de passer, men der er også andre måder.
http://ww0.java3.datastructures.net/ eller lignende bøger kan anbefales.

Ja oki, jeg fik måske ikke formuleret mig skarpt nok :) sorry.
Jeg er ikke interresseret i en reel tid for rekursive kald. Og jeg søger den matematiske måde at beregne tidskompleksiteten på.
Divide and conquer er den gældende for alle rekursive kald? Jeg mener divide and conquer halverer jo hele tiden problemet, hvorimod et rekursivt kald kalder sig selv en række gange.

yellow..det link du gav mig...jeg sys ik jeg kunne finde noget der...
Har du evt. andre? Eller måske tid til at forklare mig hvordan jeg gør :)
Vær ikke bekymret for matematikken :) Det kan jeg godt

Det er altså den assymptotiske køretid jeg er interresseret i

Linket var bare til en bog, der dækker emnet godt - men den skal selvfølgelig købes først ;-)

Ellers er der mange ressourcer på nettet på en alm. google søgning.
Fandt et par links (det første dækker de forskellige metoder meget godt).
http://www.cs.nyu.edu/courses/fall02/V22.0310-002/lectures/lecture-25.html
http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic4/

Her er f.eks. et godt eksempel på hvordan tidskompleksiteten udregnes for 2 fibonacci programmer - 1 "lineært" program og et rekursivt...

http://www.brpreiss.com/books/opus5/html/page75.html

ja oki...jeg kan godt udregne asymptotiske køretider for normale programmer :)
Det er ikke så svært, men det er bare de rekurssive det kniber med hehe. Men tak for det :)

I det eksempel jeg linkede til er program nr2 rekursivt - og de viser hele udregningen af kompleksiteten.

ups :p
Cool der var jeg vidst lige lidt hurtig der hæhæ :)
kigger lige igen

Du gør det ved at tænke dig om
    int summa ( int n ) {
        if ( n > 0 ) {
            return n + summa( n-1 );
        } else {
            return 0;
        }
    }
funktionen kalder sig selv præcis een gang for hver gang n tælles ned, så køretiden er O(N). Det er helt fint.

    int fibbo ( int n ) {
        if ( n > 1 ) {
            return fibbo( n-1 ) + fibbo( n-2 );
        } else {
            return n;
        }
    }
funktionen kalder sig selv 2 gange i hvert kald så køretiden er O(2^N).  Det er en exponentiel stigning så det bør nok kodes anderleds.

Men det er simple eksempler. metoden quicksort fx kalder også sig selv 2 gange pr rekursivt kald. men til gengæld er antallet af rekursive kald begrænset (antal elementer der skal sorteres deles i to for hver rekursion). Så alt ialt er quicksort en O(N*logN) algoritme. Og det er jo ikke alt for sølle. (i gennemsnit; dens worstcase er skrækkelig)

Det kan være noget af et hovedbrud at regne det ud. Hvis du har en konkret rekursiv funktion kan jeg prøve og kommentere udregningen for den funktion.

mvh JakobA

Superlækre svar :)
Tak for hjælpen...læg et et svar og jeg deler point ud :)

Tak :-)