Simuleren met behulp van abstracte machines met algoritmen - dummies

Hoe meer bewerkingen een algoritme vereist, hoe complexer het is. Complexiteit is een maat voor efficiëntie van algoritmen in termen van tijdsbesteding, omdat elke bewerking enige tijd in beslag neemt. Met hetzelfde probleem zijn complexe algoritmen over het algemeen minder gunstig dan eenvoudige algoritmen, omdat complexe algoritmen meer tijd vergen.

Denk aan die momenten waarop snelheid van uitvoering het verschil maakt, zoals in de medische of financiële sector, of wanneer u vliegt op een automatische piloot in een vliegtuig of ruimteschip. Het meten van algoritmecomplexiteit is een uitdagende taak, hoewel noodzakelijk als u de juiste oplossing wilt gebruiken. De eerste meettechniek maakt gebruik van abstracte machines zoals de Random Access Machine (RAM).

RAM staat ook voor Random-Access Memory, het interne geheugen dat uw computer gebruikt bij het uitvoeren van programma's. Hoewel het hetzelfde acroniem gebruikt, is een Random-Access Machine iets heel anders.

Abstracte machines zijn geen echte computers, maar theoretische, computers die zich in hun functioneren voorstellen. Je gebruikt abstracte machines om te overwegen hoe goed een algoritme zou werken op een computer zonder het te testen op het echte werk, maar gebonden aan het type hardware dat je zou gebruiken. Een RAM-computer voert elementaire rekenkundige bewerkingen uit en communiceert met informatie in het geheugen, meer niet. Telkens wanneer een RAM-computer iets doet, duurt het een tijdstap (een tijdseenheid). Wanneer u een algoritme in een RAM-simulatie evalueert, telt u de tijdstappen volgens de volgende procedure:

1. Tel elke eenvoudige bewerking (rekenkundige) als een tijdstap.
2. Splits complexe bewerkingen in eenvoudige rekenkundige bewerkingen en teltijdstappen zoals gedefinieerd in Stap 1.
3. Tel elke gegevenstoegang uit het geheugen als één tijdstap.

Om deze accounting uit te voeren, schrijft u een pseudocodeversie van uw algoritme en voert u deze stappen uit met papier en potlood. Uiteindelijk is het een eenvoudige benadering gebaseerd op een basisidee van hoe computers werken, een nuttige benadering die u kunt gebruiken om oplossingen te vergelijken ongeacht de kracht en snelheid van uw hardware of de programmeertaal die u gebruikt.

Het gebruik van een simulatie verschilt van het uitvoeren van het algoritme op een computer omdat u een standaard en vooraf gedefinieerde invoer gebruikt. Voor echte computermetingen moet u de code uitvoeren en de tijd controleren die nodig is om het uit te voeren. Running code op een computer is eigenlijk een benchmark, een andere vorm van efficiëntiemeting, waarbij u ook rekening houdt met de applicatie-omgeving (zoals het gebruikte type hardware en de software-implementatie).Een benchmark is nuttig maar ontbreekt aan generalisatie. Overweeg bijvoorbeeld hoe nieuwere hardware snel een algoritme kan uitvoeren dat eeuwen heeft geduurd op uw vorige computer.