Video: La Finale della Startup Competition 2019 - La competizione più grande d'Italia 2025
Più operazioni richiede un algoritmo, più è complesso. La complessità è una misura dell'efficienza dell'algoritmo in termini di utilizzo del tempo poiché ogni operazione richiede del tempo. Dato lo stesso problema, gli algoritmi complessi sono generalmente meno favorevoli rispetto agli algoritmi semplici perché gli algoritmi complessi richiedono più tempo.
Pensa a quei momenti in cui la velocità di esecuzione fa la differenza, come nel settore medico o finanziario, o quando voli con un pilota automatico su un aereo o un razzo spaziale. La complessità dell'algoritmo di misurazione è un compito impegnativo, anche se necessario se si desidera utilizzare la soluzione giusta. La prima tecnica di misurazione utilizza macchine astratte come la Random Access Machine (RAM).
RAM è anche l'acronimo di Random-Access Memory, ovvero la memoria interna utilizzata dal computer quando si eseguono programmi. Anche se usa lo stesso acronimo, una macchina ad accesso casuale è qualcosa di completamente diverso.
Le macchine astratte non sono computer reali, ma teorici, computer immaginati nel loro funzionamento. Usi macchine astratte per valutare quanto un algoritmo funzionerebbe su un computer senza testarlo sulla cosa reale, ma vincolato dal tipo di hardware che useresti. Un computer RAM esegue operazioni aritmetiche di base e interagisce con le informazioni in memoria, tutto qui. Ogni volta che un computer RAM fa qualcosa, richiede un passo temporale (una unità di tempo). Quando si valuta un algoritmo in una simulazione RAM, vengono conteggiati i passaggi temporali utilizzando la seguente procedura:
- Contare ogni operazione semplice (aritmetica) come un passo temporale.
- Spezza le operazioni complesse in semplici operazioni aritmetiche e calcola i passi temporali come definito al punto 1.
- Conta ogni accesso ai dati dalla memoria come un passo temporale.
Per eseguire questa contabilità, scrivi una versione pseudocodice del tuo algoritmo ed esegui questi passaggi usando carta e matita. Alla fine, si tratta di un approccio semplice basato su un'idea di base su come funzionano i computer, un'approssimazione utile che è possibile utilizzare per confrontare soluzioni indipendentemente dalla potenza e dalla velocità dell'hardware o dal linguaggio di programmazione che si utilizza.
L'uso di una simulazione è diverso dall'esecuzione dell'algoritmo su un computer perché si utilizza un input standard e predefinito. Le misurazioni con un computer reale richiedono l'esecuzione del codice e la verifica del tempo necessario per eseguirlo. L'esecuzione di codice su un computer è in realtà un punto di riferimento, un'altra forma di misurazione dell'efficienza, in cui si tiene conto anche dell'ambiente di applicazione (come il tipo di hardware utilizzato e l'implementazione del software).Un benchmark è utile ma manca la generalizzazione. Si consideri, ad esempio, in che modo un hardware più recente può eseguire rapidamente un algoritmo che impiega anni sul tuo computer precedente.
