eksponentiel tid

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

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

#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?

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
 

se http://en.wikipedia.org/wiki/NP-hard og http://mathworld.wolfram.com/NP-Problem.html

Ved nærmere eftertanke den sidste i #4 med primtal holder vist ikke

Der findes et lidt absurd eksempel. Fibonaccitallene er defineret ved: F₀ = 0, F₁ = 1, F_n = F_n-1 + F_n-2.

Et program til at beregne F_m 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(e^m), 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(eⁿ) 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.