Algoritmi Per Dummies Cheat Sheet - dummies

di John Paul Mueller, Luca Massaron

Gli algoritmi non devono essere noiosi o difficili da usare. In effetti, gli algoritmi ti circondano in molti modi che potresti non aver pensato, e li usi ogni giorno per svolgere compiti importanti. Tuttavia, è necessario essere in grado di utilizzare algoritmi senza dover diventare un matematico.

I linguaggi di programmazione consentono di descrivere i passaggi utilizzati per creare un algoritmo. Alcune lingue sono migliori di altre nello svolgere questo compito in un modo che le persone possono comprendere senza diventare informatici. Python semplifica l'utilizzo degli algoritmi perché include un sacco di supporto integrato ed esteso (attraverso l'uso di pacchetti, set di dati e altre risorse). Questo Cheat Sheet ti aiuta ad accedere ai suggerimenti più comuni per rendere l'utilizzo degli algoritmi semplice e veloce.

Individuazione dell'algoritmo necessario

La seguente tabella descrive algoritmi e tipi di algoritmi che potrebbero essere utili per vari tipi di analisi dei dati. (È possibile trovare discussioni su tutti questi algoritmi in Algorithms For Dummies.)

Algorithm	Descrizione	Link utili
A * Cerca	L'algoritmo tiene traccia del costo dei nodi mentre li esplora utilizzando il equazione: f (n) = g (n) + h (n), dove: n è l'identificatore di nodo g (n) è il costo per raggiungere il nodo fino ad ora h (n) è il costo stimato per raggiungere il l'obiettivo dal nodo f (n) è il costo stimato del percorso da n all'obiettivo L'idea è di cercare prima i percorsi più promettenti ed evitare percorsi costosi.	Standford. edu
Albero bilanciato	Un tipo di albero che mantiene una struttura equilibrata attraverso la riorganizzazione in modo che possa fornire tempi di accesso ridotti. Il numero di elementi sul lato sinistro differisce dal numero sul lato destro di uno al massimo.	Webdocs
Ricerca bidirezionale	Questa tecnica esegue la ricerca simultanea dal nodo radice e dal nodo obiettivo finché i due percorsi di ricerca non si incontrano nel mezzo. Un vantaggio di questo approccio è che è efficiente nel tempo perché trova la soluzione più veloce di molte altre soluzioni a forza bruta. Inoltre, utilizza la memoria in modo più efficiente rispetto ad altri approcci e trova sempre una soluzione. Il principale svantaggio è la complessità di implementazione.	Pianificazione. cs
Albero binario	Questo è un tipo di albero che contiene nodi che si connettono a zero (nodi foglia), uno o due nodi (nodi ramo) altri nodi. Ogni nodo definisce i tre elementi che deve includere per fornire connettività e memorizzare i dati: archiviazione dei dati, connessione a sinistra e connessione corretta.	cs. CMU. edu
Ricerca per ampiezza	Questa tecnica inizia dal nodo radice, esplora prima ciascuno dei nodi figli e solo dopo passa al livello successivo. Progredisce livello per livello fino a quando non trova una soluzione. Lo svantaggio di questo algoritmo è che deve memorizzare ogni nodo in memoria, il che significa che utilizza una notevole quantità di memoria per un gran numero di nodi. Questa tecnica può verificare la presenza di nodi duplicati, risparmiando tempo e sempre con una soluzione.	Khan Academcy
Brute Force	Questa è una tecnica di problem solving in cui qualcuno prova ogni possibile soluzione, cercando la soluzione migliore. Le tecniche a forza bruta garantiscono una soluzione ottimale quando ce n'è una, ma richiedono molto tempo per essere implementate e la maggior parte delle persone le evita.	Igm. univ
First Depth-Search	Questa tecnica inizia dal nodo radice ed esplora una serie di nodi figli connessi fino a raggiungere un nodo foglia. Progredisce ramo dopo ramo finché non trova una soluzione. Lo svantaggio di questo algoritmo è che non è possibile verificare la presenza di nodi duplicati, il che significa che potrebbe attraversare gli stessi percorsi dei nodi più di una volta. In effetti, questo algoritmo potrebbe non trovare affatto una soluzione, il che significa che è necessario definire un punto limite per mantenere l'algoritmo dalla ricerca infinita. Un vantaggio di questo approccio è che è efficiente in termini di memoria.	Hacker Earth
Dividi e Conquista	Questa è una tecnica di problem solving in cui il problema è suddiviso in parti più piccole possibili e risolto utilizzando l'approccio più semplice possibile. Questa tecnica consente di risparmiare tempo e risorse considerevoli rispetto ad altri approcci, come la forza bruta. Tuttavia, non sempre garantisce un risultato ottimale.	Khan Academy
Dijikstra	Questo è un algoritmo utilizzato per trovare il percorso più breve in un grafico diretto, ponderato (con pesi positivi).	Geeks for Geeks
Graph	Un grafico è una sorta di estensione di un albero. Come per gli alberi, hai nodi che si connettono tra loro per creare relazioni. Tuttavia, a differenza degli alberi binari, un grafico può avere più di una o due connessioni. In effetti, i nodi dei grafici hanno spesso una moltitudine di connessioni. Vedete grafici usati in luoghi come le mappe per il GPS e tutti i tipi di altri luoghi per i quali l'approccio top-down di un albero non funzionerà.	Esercizi
Algoritmi golosi	Thistechnique di uno dei problem solving in cui la soluzione si basa sulla migliore risposta per ogni fase del processo di problem-solving. Gli algoritmi greedy generalmente fanno due presupposti: È possibile effettuare un'unica scelta ottimale in un dato passaggio. Scegliendo la selezione ottimale in ogni fase, è possibile trovare una soluzione ottimale per il problema generale.	Tutorial
Greedy Best-First Search (BFS)	L'algoritmo sceglie sempre il percorso più vicino all'obiettivo utilizzando l'equazione: f (n) = h (n). Questo particolare algoritmo può trovare soluzioni abbastanza rapidamente, ma può anche rimanere bloccato nei loop, quindi molte persone non lo considerano un approccio ottimale per trovare una soluzione.	Centurion2
Hashing	Questo è un metodo per predire la posizione di un particolare oggetto dati nella struttura dati (qualunque sia la struttura) prima di cercarlo effettivamente. Questo approccio si basa sull'uso di chiavi inserite in un indice. Una funzione di hash trasforma la chiave in un valore numerico che l'algoritmo inserisce in una tabella hash. Una tabella hash fornisce i mezzi per creare un indice che punti agli elementi in una struttura dati in modo che un algoritmo possa facilmente prevedere la posizione dei dati.	Tutorial
Heap	Questo è un albero sofisticato che consente l'inserimento di dati nella struttura ad albero. L'utilizzo dell'inserimento dei dati rende più veloce l'ordinamento. È possibile classificare ulteriormente questi alberi come quantità massime di heap e min in base alla capacità dell'albero di fornire immediatamente il valore massimo o minimo presente nell'albero.	Esercitazioni
Euristica	Questa è una tecnica di problem solving che si basa sulla scoperta di sé e produce risultati sufficientemente utili (non necessariamente ottimali, ma abbastanza buoni) per affrontare un problema abbastanza bene che una soluzione migliore non è t necessario. L'auto-scoperta è il processo che consente all'algoritmo di mostrarti un percorso potenzialmente utile per una soluzione (ma devi comunque contare sull'intuizione e sulla comprensione umana per sapere se la soluzione è quella giusta).	nord-ovest. edu
MapReduce	Questo è un framework per far funzionare gli algoritmi usando i calcoli in parallelo (usando più computer collegati insieme in una rete), consentendo agli algoritmi di completare le loro soluzioni più velocemente.	Hadoop Apache
Mergesort	Mergesort è un metodo di ordinamento basato su un confronto generale. Dipende da un approccio divide et impera nello svolgimento del proprio compito.	Geeks for Geeks
Nash Equilibrium	Questa è una teoria di gioco in cui gli altri giocatori conoscono la strategia di equilibrio per gli altri giocatori, quindi nessuno ha nulla da guadagnare cambiando la sua strategia personale. Questa teoria vede l'uso in qualsiasi situazione ostile in cui il giocatore deve rendere conto delle decisioni prese da tutti gli altri giocatori per vincere la partita.	Khan Academy
PageRank	PageRank è un algoritmo per misurare l'importanza di un nodo in un grafico. Questo algoritmo è alla base degli algoritmi principali di Google per l'attivazione di ricerche pertinenti per gli utenti.	Princeton. edu
Ricerca euristica pura	Questo algoritmo espande i nodi in ordine di costo. Mantiene due liste. L'elenco chiuso contiene i nodi che ha già esplorato e l'elenco aperto contiene i nodi che deve ancora esplorare. In ogni iterazione, l'algoritmo espande il nodo con il costo più basso possibile. Tutti i nodi figlio vengono inseriti nell'elenco chiuso e vengono calcolati i costi dei singoli nodi figlio. L'algoritmo invia i nodi figli con un costo ridotto alla lista aperta ed elimina i nodi figlio con un costo elevato. Di conseguenza, l'algoritmo esegue una ricerca intelligente e basata sui costi per la soluzione.	World of Computing
Quicksort	Questa è una strategia di ordinamento per uso generico basata sul partizionamento di matrici di dati in array più piccoli.Dipende da un approccio divide et impera nello svolgimento del proprio compito.	Esercitazioni
Albero sbilanciato	Questo è un albero che posiziona i nuovi elementi di dati laddove necessario nell'albero senza considerare l'equilibrio. Questo metodo di aggiunta di elementi rende la costruzione dell'albero più veloce ma riduce la velocità di accesso durante la ricerca o l'ordinamento.	Quora

Differenziamento di algoritmi da altre strutture matematiche

Se sei come la maggior parte delle persone, spesso ti ritrovi a grattarti la testa quando si tratta di strutture matematiche perché nessuno sembra sapere come usare correttamente i termini. È come se le persone cercassero intenzionalmente di rendere le cose difficili! Dopo tutto, cos'è un'equazione e perché è diversa da un algoritmo? Bene, non temere più: la seguente tabella fornisce la guida definitiva alle strutture matematiche che potresti incontrare ma che hanno avuto paura di chiedere.

Struttura	Descrizione
Equazione	Numeri e simboli che, se presi nel loro insieme, equivalgono a un valore specifico. Un'equazione contiene sempre un segno di uguale in modo da sapere che i numeri e i simboli rappresentano il valore specifico sull'altro lato del segno di uguale. Le equazioni contengono generalmente informazioni variabili presentate come simbolo, ma non sono richieste per utilizzare le variabili.
Formula	Una combinazione di numeri e simboli utilizzati per esprimere informazioni o idee. Una formula normalmente presenta concetti matematici o logici, tali da definire il più grande divisore comune (GCD) di due interi (il video di Khan Academy dice come funziona). Generalmente, una formula mostra la relazione tra due o più variabili. La maggior parte delle persone vede una formula come un tipo speciale di equazione.
Algorithm	Una sequenza di passaggi usati per risolvere un problema. La sequenza presenta un metodo unico per risolvere un problema fornendo una soluzione particolare. Un algoritmo non deve rappresentare concetti matematici o logici, anche se le presentazioni in questo libro spesso rientrano in quella categoria perché le persone utilizzano più comunemente algoritmi in questo modo. Alcune formule speciali sono anche algoritmi, come la formula quadratica. Affinché un processo possa rappresentare un algoritmo, deve essere il seguente: Finito: L'algoritmo deve alla fine risolvere il problema. Ben definito: La serie di passaggi deve essere precisa e presentare passaggi comprensibili, soprattutto da parte dei computer, che devono essere in grado di creare un algoritmo utilizzabile. Effettivo: Un algoritmo deve risolvere tutti i casi del problema per il quale qualcuno lo ha definito. Un algoritmo dovrebbe sempre risolvere il problema che deve risolvere. Anche se è necessario prevedere alcuni guasti, l'incidenza del fallimento è rara e si verifica solo in situazioni accettabili per l'uso previsto dell'algoritmo.

Modi sorprendenti per utilizzare algoritmi

Le persone utilizzano in realtà algoritmi tutto il tempo. Ad esempio, fare toast è un esempio di un algoritmo, come spiegato in questo post del blog. Fare toast non è un algoritmo sorprendente, ma quelli nella tabella seguente, che usano un computer per eseguire compiti, lo sono.

Attività	Perché è sorprendente
Crittografia	Mantenere i dati al sicuro è una battaglia continua con gli hacker che attaccano costantemente le fonti di dati. Gli algoritmi consentono di analizzare i dati, inserirli in qualche altra forma e quindi riportarli alla sua forma originale in un secondo momento.
Analisi del grafico	La capacità di decidere sulla linea più breve tra due punti trova tutti i tipi di utilizzo. Ad esempio, in un problema di routing, il tuo GPS non potrebbe funzionare senza questo particolare algoritmo perché non potrebbe mai indirizzarti lungo le strade della città usando il percorso più breve dal punto A al punto B.
Generazione di numeri pseudocasuali	Immagina di giocare che non è mai cambiato. Si inizia nello stesso punto e si eseguono gli stessi passaggi nello stesso modo ogni volta che si gioca. Noioso! Senza la capacità di generare numeri apparentemente casuali, molti compiti del computer diventano inutili o impossibili.
Pianificazione	Rendere l'uso delle risorse equo per tutti gli interessati è un altro modo in cui gli algoritmi rendono nota la loro presenza in modo significativo. Ad esempio, le luci di cronometraggio alle intersezioni non sono più semplici dispositivi che contano i secondi tra le variazioni di luce. I dispositivi moderni prendono in considerazione tutti i tipi di problemi, ad esempio l'ora del giorno, le condizioni meteorologiche e il flusso di traffico. La pianificazione arriva in molte forme, tuttavia. Considera in che modo il tuo computer esegue più attività contemporaneamente. Senza un algoritmo di pianificazione, il sistema operativo potrebbe afferrare tutte le risorse disponibili e impedire all'applicazione di svolgere qualsiasi lavoro utile.
Ricerca	Individuare le informazioni o verificare che le informazioni visualizzate siano quelle desiderate, è un compito essenziale. Senza questa funzionalità, molte attività eseguite online non sarebbero possibili, come trovare il sito Web su Internet che vende la caffettiera perfetta per il tuo ufficio.
Ordinamento	Determinare l'ordine in cui presentare le informazioni è importante perché la maggior parte delle persone oggi soffre di sovraccarico di informazioni e deve ridurre la quantità di dati. Immagina di andare in Amazon, trovando più di mille caffettiere in vendita, e tuttavia non essere in grado di ordinarle in base al prezzo o alla recensione più positiva. Inoltre, molti algoritmi complessi richiedono dati nell'ordine corretto per funzionare in modo affidabile, quindi l'ordinamento è un requisito importante per risolvere più problemi.
Trasformare	La conversione di un tipo di dati in un altro tipo di dati è fondamentale per comprendere e utilizzare i dati in modo efficace. Ad esempio, potresti capire bene i pesi imperiali, ma tutte le tue fonti usano il sistema metrico. La conversione tra i due sistemi consente di comprendere i dati. Allo stesso modo, la Fast Fourier Transform (FFT) converte i segnali tra il dominio del tempo e il dominio della frequenza, consentendo a cose come il tuo router WiFi di funzionare.

Gestire la complessità degli algoritmi

Sai già che gli algoritmi sono complessi. Tuttavia, è necessario sapere quanto è complesso un algoritmo perché più è complesso, più tempo è necessario per l'esecuzione. La seguente tabella ti aiuta a capire i vari livelli di complessità presentati in ordine di tempo di esecuzione (dal più veloce al più lento).

Complessità	Descrizione
Complessità costante O (1)	Fornisce un tempo di esecuzione invariabile, indipendentemente dalla quantità di input fornita. Ogni input richiede una singola unità di tempo di esecuzione.
Complessità logaritmica O (log n)	Il numero di operazioni cresce a un ritmo più lento dell'input, rendendo l'algoritmo meno efficiente con piccoli input e più efficiente con quelli più grandi. Un algoritmo tipico di questa classe è la ricerca binaria.
Complessità lineare O (n)	Le operazioni crescono con l'input in un rapporto 1: 1. Un algoritmo tipico è l'iterazione quando si esegue la scansione di input una volta e si applica un'operazione a ciascun elemento di esso.
Complessità Linearitmica O (n log n)	La complessità è un mix tra complessità logaritmica e lineare. È tipico di alcuni algoritmi intelligenti utilizzati per ordinare dati, come Mergesortsort, Heapsort e Quicksort.
Complessità quadratica O (n ² )	Le operazioni crescono come un quadrato del numero di input. Quando si ha una iterazione all'interno di un'altra iterazione (chiamata iterazioni nidificate in informatica), si ha una complessità quadratica. Ad esempio, hai un elenco di nomi e, per trovare quelli più simili, confronti ciascun nome con tutti gli altri nomi. Alcuni algoritmi di ordinamento meno efficienti presentano tale complessità: ordinamento di bolle, ordinamento di selezione e ordinamento di inserimento. Questo livello di complessità significa che i tuoi algoritmi possono essere eseguiti per ore o addirittura giorni prima di raggiungere una soluzione.
Complessità cubica O (n ³ )	Le operazioni crescono anche più rapidamente della complessità quadratica perché ora si hanno più iterazioni nidificate. Quando un algoritmo ha questo ordine di complessità ed è necessario elaborare una modesta quantità di dati (100.000 elementi), l'algoritmo potrebbe funzionare per anni. Quando si dispone di un numero di operazioni che è una potenza dell'input, è comune fare riferimento all'algoritmo come in esecuzione in tempo polinomiale.
Complessità esponenziale O (2 ⁿ )	L'algoritmo richiede il doppio del numero di operazioni precedenti per ogni nuovo elemento aggiunto. Quando un algoritmo ha questa complessità, anche piccoli problemi possono richiedere per sempre. Molti algoritmi che eseguono ricerche esaurienti hanno una complessità esponenziale. Tuttavia, l'esempio classico di questo livello di complessità è il calcolo dei numeri di Fibonacci.
Complessità fattoriale O (n!)	Questo algoritmo presenta un vero incubo di complessità a causa dell'elevato numero di combinazioni possibili tra gli elementi. Immagina: se il tuo input è di 100 oggetti e un'operazione sul tuo computer richiede 10 ^-6 secondi (una velocità ragionevole per ogni computer al giorno d'oggi), avrai bisogno di circa 10 ¹⁴⁰ anni per completare l'attività con successo (una quantità di tempo impossibile perché l'età dell'universo è stimata in 10 ₁₄ anni). Un famoso problema di complessità fattoriale è il problema del commesso viaggiatore, in cui un venditore deve trovare il percorso più breve per visitare molte città e tornare alla città di partenza.