Simulera Använda abstrakta maskiner med algoritmer - dummies

Ju fler operationer en algoritm kräver desto mer komplex är den. Komplexitet är ett mått på algoritmseffektivitet när det gäller tidsanvändning eftersom varje operation tar lite tid. Med tanke på samma problem är komplexa algoritmer generellt mindre gynnsamma än enkla algoritmer eftersom komplexa algoritmer kräver mer tid.

Tänk på de tider då körningshastigheten gör skillnaden, till exempel inom medicinsk eller finansiell sektor, eller när man flyger på en automatisk pilot på en flygplan eller rymdraket. Mätningsalgoritmkomplexitet är en utmanande uppgift, men en nödvändig om du vill använda den rätta lösningen. Den första mättekniken använder abstrakta maskiner som Random Access Machine (RAM).

RAM står också för Random Access Memory, vilket är det interna minnet som datorn använder när program körs. Även om den använder samma akronym är en slumpmässig åtkomstmaskin något helt annorlunda.

Abstrakta maskiner är inte riktiga datorer, men teoretiska, datorer som föreställs i deras funktion. Du använder abstrakta maskiner för att överväga hur bra en algoritm skulle fungera på en dator utan att testa den på den riktiga saken, dock bunden av vilken maskinvara du skulle använda. En RAM-dator utför grundläggande aritmetiska operationer och interagerar med information i minnet, det är allt. Varje gång en RAM-dator gör någonting tar det ett tidssteg (en tidsenhet). När du utvärderar en algoritm i en RAM-simulering räknar du tidssteg med följande procedur:

1. Räkna varje enkel operation (aritmetiska sådana) som ett tidssteg.
2. Bryt komplexa operationer till enkla aritmetiska operationer och räkna tidssteg som definieras i steg 1.
3. Räkna varje dataåtkomst från minnet som ett steg.

För att utföra denna redovisning skriver du en pseudokodversion av din algoritm och utför dessa steg med papper och penna. I slutändan är det ett enkelt tillvägagångssätt baserat på en grundläggande ide om hur datorer fungerar, en användbar approximation som du kan använda för att jämföra lösningar oavsett maskinens kraft och hastighet eller det programmeringsspråk du använder.

Att använda en simulering skiljer sig från att köra algoritmen på en dator eftersom du använder en standard och fördefinierad ingång. Reella datormätningar kräver att du kör koden och verifiera tiden som krävs för att köra den. Körningskod på en dator är faktiskt en riktmärke, en annan form av effektivitetsmätning, där du också tar hänsyn till applikationsmiljön (t.ex. vilken typ av hårdvara som används och programmets implementering).En riktmärke är användbar men saknar generalisering. Tänk till exempel hur nyare hårdvara snabbt kan utföra en algoritm som tog åldrar på din tidigare dator.