Hvordan finne gj.snitt tid på en algoritme ?

[arna]

Spørsmål er som følger: Hvordan finner man ut hva gjennomsnitts-tiden er på en algoritme dersom man bare har koden? (Tar i utgangspunkt 2x nesta-for løkker for å eksemplifisere)

 

for (int i = 1; i i <= 10; i++)
   for(int j = 1; j <= 4; j++; )
         */ irrellevant*/ 

 

Dersom disse nesta-løkkene hadde vært kvadratiske, ville jo formelen vært O( i * j ) men hva hvis den innerste løkken er mindre/større enn den yttereste slik som ovenfor?

[sim]

Eksempelet ditt har vel konstant kjøretid (O(1)) siden det ikke er avhengig av størrelsen på input.

 

Jeg tror gjennomsnittlig kjøretid kan være ganske vanskelig å finne. Jeg har kun jobbet med worst-case (og noen best-case).

[Emancipate]

Gjennomsnittstiden kommer jo som regel an på hvilket input du har.

[Ueland]

Skal du teste f.eks algoritmer må du først og fremst kjøre algoritmen f.eks 100 000 ganger, eller mer/mindre avhengig av språk du bruker. Så er det bare å ta tiden før og etter selve jobben så vet du hvor lenge det tar