Simulând Utilizarea mașinilor abstracte cu algoritmi - dummies

Cu cât mai multe operații necesită un algoritm, cu atât este mai complexă. Complexitatea este o măsură a eficienței algoritmului în ceea ce privește utilizarea timpului deoarece fiecare operațiune durează ceva timp. Având în vedere aceeași problemă, algoritmii complexi sunt, în general, mai puțin favorabili decât algoritmii simpli, deoarece algoritmii complexi necesită mai mult timp.

Gândiți-vă la acele momente în care viteza de execuție face diferența, cum ar fi în sectorul medical sau financiar sau când zbori pe pilot automat pe o rachetă de avion sau spațiu. Măsurarea complexității algoritmului este o sarcină dificilă, deși una necesară dacă doriți să folosiți soluția potrivită. Prima tehnică de măsurare utilizează mașini abstracte precum Machine Random Access (RAM).

RAM înseamnă de asemenea memoria Random Access, care este memoria internă utilizată de computerul dvs. atunci când rulează programe. Chiar dacă utilizează același acronim, o mașină cu acces aleatoriu este ceva complet diferit.

Mașinile abstracte nu sunt calculatoare reale, ci teoretice, calculatoare imaginate în funcționarea lor. Utilizați mașini abstracte pentru a vă gândi cât de bine ar funcționa un algoritm pe un computer fără a îl testa pe chestia reală, dar legat de tipul de hardware pe care îl utilizați. Un computer RAM realizează operații aritmetice de bază și interacționează cu informațiile din memorie, asta e tot. De fiecare dată când un computer RAM face ceva, este nevoie de un pas de timp (o unitate de timp). Când evaluați un algoritm într-o simulare RAM, numărați pașii de timp utilizând următoarea procedură:

1. Numărați fiecare operație simplă (cele aritmetice) ca un pas de timp.
2. Întrerupeți operațiile complexe în operații aritmetice simple și numărați pașii de timp așa cum sunt definiți în Pasul 1.
3. Contorizați fiecare acces de date din memorie ca un pas de timp.

Pentru a efectua această contabilitate, scrieți o versiune pseudocod a algoritmului dvs. și efectuați acești pași utilizând hârtie și creion. În cele din urmă, este o abordare simplă, bazată pe o idee de bază privind funcționarea computerelor, o aproximație utilă pe care o puteți utiliza pentru a compara soluțiile indiferent de puterea și viteza hardware-ului dvs. sau a limbajului de programare pe care îl utilizați.

Folosirea unei simulări diferă de a rula algoritmul pe un computer deoarece utilizați o intrare standard și predefinită. Măsurătorile reale ale computerului necesită rularea codului și verificarea timpului necesar pentru a-l rula. Codul de rulare pe un computer este de fapt un punct de referință, o altă formă de măsurare a eficienței, în care, de asemenea, țineți cont de mediul aplicației (cum ar fi tipul de hardware utilizat și implementarea software-ului).Un punct de referință este util, dar nu are generalizare. Luați în considerare, de exemplu, modul în care hardware-ul mai nou poate executa rapid un algoritm care a îmbătrânit pe computerul anterior.