IT
eksponentiel tid
Er der nogen der kan give et konkret eksempel på et lille program som har en eksponentiel tidskompleksitet?
Svar #1
05. juli 2014 af peter lind
Hvad mener du med eksponentiel tidskompleksitet ?
I teletrafik regner man ofte med at tiden for en samtale er eksponentiel fordelt eller med andre ord at afgangen af samtaler er eksponentiel fordelt
Svar #2
05. juli 2014 af thomaslarsen90Arocketmailcom (Slettet)
Tiden det tager for et program at beregne et matematisk udtryk.
Fx f(x)=x+2
Hvor lang tid vil det så tage programmet at beregne f(2) ? Det tager lineært lang tid... så hvordan finder vi et udtryk der tager eksponentielt lang tid at beregne
Svar #3
05. juli 2014 af Andersen11 (Slettet)
#2
Hvad mener du med, at det tager lineært lang tid? Programmet skal bruge ca den samme tid til at beregne f(x) = x+2 for ethvert x. Beregningstiden er med god tilnærmelse uafhængig af x.
En algoritme, der for eksempel beregner determinanten af en kvadratisk n×n matrix, vil i beregningstiden afhænge af n. Måske er den den problemstilling, du sigter til?
Svar #4
05. juli 2014 af peter lind
Så skal du snarere have fat i algoritmer
Simplex algoritmen er sådan et eksempel.
Heltals lineære programmering er også sådan et eksempel
Jeg tror også at at hvis man skal finde samtlige primyal mindre end n vokser antallet af iterationer eksponentielt med n
Svar #5
05. juli 2014 af peter lind
Svar #6
05. juli 2014 af peter lind
Ved nærmere eftertanke den sidste i #4 med primtal holder vist ikke
Svar #7
11. juli 2014 af Eksperimentalfysikeren
Der findes et lidt absurd eksempel. Fibonaccitallene er defineret ved: F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2.
Et program til at beregne Fm for givet m kan skrives på to forskellige måder. Den itterative, hvor man hele tiden "husker" de to foregående værdier og beregner den næste. Dens tidskompleksitet er O(m), altså lineær.
Den anden metode er en rekursiv metode. Man skriver en funktion, der for m∈{0,1} giver de to angivne værdier. For m>1 kalder funktionen sig selv for at få de to foregående værdier. Man kan vise, at tidskompleksiteten er O(em), altså eksponentiel.
Eksemplet benyttes til at vise, at selv om man i nogle tilfælde kan have stor nytte af rekursiv programmering, skal man ikke bruge det ukritisk. Desværre bruges det også til at skræmme nogle helt fra at bruge rekursion, men det er helt grundløst.
Der findes en samling problemer, for hvilke der kun kendes O(en) algoritmer,men der findes endnu ikke bevis for, at de kun har algoritmer af denne tidskompleksitet. Et af dem handler om en handelsrejsende, der søger den korteste rute han kan benytte for at besøge n byer. En interessant ting er, at kan man finde en mindre tidskompleks algoritme for ét af problemerne, kan den omformes til tilsvarende algoritmer for de andre problemer.
Skriv et svar til: eksponentiel tid
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.