"Dcasso" <ikke@oplyst_pga_spam.dk> wrote in message
news:po7rmvg4ff3e19h81c6hvj0jijs51paeed@4ax.com...
> Hej
>
> Er der nogle der ligger inde med noget algoritmeanalyse for dummies :)
> Føler mig ret lost i det, og kunne egentlig godt tænke mig at se en
> anden vinkel på det, end den mark allan weiss giver.
> Så ligger i inde med noget godt materiale fra forelæsninger, anden
> litteratur på nettet el. lign. vil jeg meget gerne høre om det.
>
> Årsagen til at det er placeret i denne gruppe, er selvfølgelig at jeg
> helst ser det indenfor java, da det er her mit behov ligger.
Hvis du mener du analyse af tids- og pladskompleksitet, så vil jeg vove at
sige 1) at kompleksitetsanalyse er uafhængigt af sproget, og 2) Java er et
dårligt udgangspunkt for kompleksitetsanalyse.
Det lyder naturligvis modstridende; men meningen der følgende:
1) Kompleksiteten af et program er vel defineret som den mændge af resourcer
et program skal bruge for at gennemføre en beregning, som funktion af
størrelsen af input. Hvis vi snakker om tidskompleksitet, så handler det
altså om hvor mange simple operationer der skal udføres, hvor en simpel
operation antages at tage konstant tid (en CPU-cykel?).
Derfor handler det ikke så meget om hvilket sprog programmet er skrevet i,
som det handler om hvad programmet gør i generelle termer af tildelinger,
løkker og betingelser (altså if-sætninger).
2) Nu da Java er et fortolket sprog, med en bagvedliggende virtuel maskine
som optimerer på livet løs, så er det ikke sikkert at "en løkke bare er en
løkke", hvorfor den reelle udførsel af et program måske nok har en teoretisk
worst-case tidskompleksitet, men hvor en række kørsler kan afsløre en helt
andet opførsel af programmet.
Et eksempel herpå er et par algoritmer jeg implementerede den anden dag, som
handlede om en løsning med dynamisk programmering vs en løsning med
(plads)optimeret dynamisk programmering.
Meningen var, at jeg ville se opførslen af en O(n^2)-algoritme, hvor en
pladsoptimering gør at man kan opnå lineært- i stedet for kvadratisk
pladsforbrug, ved at bruge dobbelt tid. Men, min Java-implementation viste
faktisk at den (plads)optimerede algoritme altid var hurtigere end den
almindelige løsning med dynamisk programmering. Irriterende(!)(?)
Nu vil jeg i stedet implementere algoritmen i C, så jeg kan få den dejligt
illustrative udførselstid jeg vil have.
Kildekoden kan i øvrigt ses her:
http://www.daimi.au.dk/~lasse/kurser/dAiB/project1/
Mvh Lasse
--
Lasse Westh-Nielsen
lasse@daimi.au.dk