Simulering Brug af abstrakte maskiner med algoritmer - dummier

Jo flere operationer en algoritme kræver, jo mere kompleks er den. Kompleksitet er et mål for algoritme effektivitet i form af tidsforbrug, fordi hver operation tager noget tid. På grund af det samme problem er komplekse algoritmer generelt mindre gunstige end simple algoritmer, fordi komplekse algoritmer kræver mere tid.

Tænk på de tidspunkter, hvor udførelseshastigheden gør forskellen, som f.eks. I medicinsk eller finansiel sektor, eller når du flyver på automatisk pilot på et fly eller rumraket. Måling af algoritme kompleksitet er en udfordrende opgave, selv om det er nødvendigt, hvis du vil anvende den rigtige løsning. Den første måle teknik bruger abstrakte maskiner som Random Access Machine (RAM).

RAM står også for Random Access Memory, som er den interne hukommelse, som din computer bruger, når du kører programmer. Selvom det bruger samme akronym, er en tilfældig adgangsmaskine noget helt anderledes.

Abstrakte maskiner er ikke rigtige computere, men teoretiske, computere, der forestiller sig i deres funktion. Du bruger abstrakte maskiner til at overveje, hvor godt en algoritme ville arbejde på en computer uden at teste den på den rigtige ting, men bundet af den type hardware, du ville bruge. En RAM-computer udfører grundlæggende aritmetiske operationer og interagerer med information i hukommelsen, det er alt. Hver gang en RAM-computer gør noget, tager det et tidstrin (en tidsenhed). Når du vurderer en algoritme i en RAM-simulering, tæller du tidstrin ved hjælp af følgende procedure:

1. Tæl hver enkel operation (aritmetiske) som et tidstrin.
2. Bryd komplekse operationer til simple aritmetiske operationer og tæl tidsteg som defineret i trin 1.
3. Tæl alle dataadgang fra hukommelsen som en gangstrin.

For at udføre denne bogføring, skriver du en pseudokodeversion af din algoritme og udfører disse trin ved hjælp af papir og blyant. I sidste ende er det en simpel tilgang baseret på en grundlæggende ide om, hvordan computere fungerer, en nyttig tilnærmelse, som du kan bruge til at sammenligne løsninger uanset maskinens strøm og hastighed eller det programmeringssprog, du bruger.

Brug af en simulation er forskellig fra at køre algoritmen på en computer, fordi du bruger en standard og foruddefineret indgang. Reelle computer målinger kræver, at du kører koden og verificerer den tid, der kræves for at køre den. Kørselskode på en computer er faktisk en benchmark, en anden form for effektivitetsmåling, hvor du også tegner for applikationsmiljøet (såsom den anvendte hardware og softwareimplementeringen).Et benchmark er nyttigt, men mangler generalisering. Overvej f.eks., Hvordan nyere hardware hurtigt kan udføre en algoritme, der tog aldre på din tidligere computer.