Video: Moleman 2 - Demoscene - The Art of the Algorithms (2012) 2024
Jo flere operasjoner en algoritme krever, jo mer kompleks er det. Kompleksitet er et mål for algoritmenes effektivitet når det gjelder tidsbruk fordi hver operasjon tar litt tid. Gitt det samme problemet, er komplekse algoritmer generelt mindre gunstige enn enkle algoritmer fordi komplekse algoritmer krever mer tid.
Tenk på de tidspunktene hvor utførelseshastigheten gjør forskjellen, som for eksempel i medisinsk eller finansiell sektor, eller når du flyr på automatisk pilot på et fly eller romraket. Målealgoritmkompleksitet er en utfordrende oppgave, om nødvendig, hvis du vil benytte den riktige løsningen. Den første målingsteknikken bruker abstrakte maskiner som Random Access Machine (RAM).
RAM står også for Random Access Memory, som er internminnet som datamaskinen bruker når du kjører programmer. Selv om den bruker samme akronym, er en tilfeldig tilgangsmaskin noe helt annerledes.
Abstrakte maskiner er ikke ekte datamaskiner, men teoretiske, datamaskiner som er forestilt i deres funksjon. Du bruker abstrakte maskiner til å vurdere hvor bra en algoritme ville fungere på en datamaskin uten å teste den på den virkelige tingen, men avhengig av hvilken type maskinvare du vil bruke. En RAM-datamaskin utfører grunnleggende aritmetiske operasjoner og samhandler med informasjon i minnet, det er alt. Hver gang en RAM-datamaskin gjør noe, tar det et tidsteg (en tidsenhet). Når du vurderer en algoritme i en RAM-simulering, teller du tidspunkter ved å bruke følgende fremgangsmåte:
- Telle hver enkel operasjon (aritmetiske) som et tidstrinn.
- Koble komplekse operasjoner til enkle aritmetiske operasjoner og telle tidstrinn som definert i trinn 1.
- Telle all dataadgang fra minnet som en gangsteg.
For å utføre denne regnskapet, skriver du en pseudokodeversjon av algoritmen din og utfører disse trinnene ved hjelp av papir og blyant. Til slutt er det en enkel tilnærming basert på en grunnleggende ide om hvordan datamaskiner fungerer, en nyttig tilnærming som du kan bruke til å sammenligne løsninger uavhengig av maskinens kraft og hastighet eller programmeringsspråket du bruker.
Bruke en simulering er forskjellig fra å kjøre algoritmen på en datamaskin fordi du bruker en standard og forhåndsdefinert inngang. Ekte datamålinger krever at du kjører koden og kontrollerer tiden som kreves for å kjøre den. Kjørekode på en datamaskin er faktisk en referanse, en annen form for effektivitetsmåling, hvor du også tar hensyn til applikasjonsmiljøet (for eksempel typen maskinvare som brukes og programvareimplementeringen).Et referansepunkt er nyttig, men mangler generalisering. Tenk for eksempel hvordan nyere maskinvare raskt kan utføre en algoritme som tok aldre på din tidligere datamaskin.
