Miscellanea

Complessità temporale: perché alcuni algoritmi funzionano per miliardi di anni

Complessità temporale: perché alcuni algoritmi funzionano per miliardi di anni


We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.

Questo è il terzo articolo di una serie in sette parti su algoritmi e calcolo, che esplora come utilizziamo semplici numeri binari per alimentare il nostro mondo. Il primo articolo, Come gli algoritmi gestiscono il mondo in cui viviamo, può essere trovato qui.

Se guardi una visualizzazione di diversi algoritmi di ordinamento che lavorano su un set di dati, diventa molto ovvio, molto rapidamente, che alcuni sono molto migliori di altri. Dove prende un algoritmo secondi per finire, un altro prenderà minuti anche con piccoli set di dati. Fortunatamente, non abbiamo bisogno di vedere l'algoritmo al lavoro per sapere se l'algoritmo può portare a termine il lavoro rapidamente o se crollerà sotto il peso del suo input. Quello è ciò che Notazione O grande è per e può dirci a colpo d'occhio se il file Complessità temporale di un algoritmo significa che lo otterremo in pochi ore o miliardi di anni.

Cos'è la complessità temporale?

In termini più formali, complessità temporale è la misura di quanto tempo ci vorrà per produrre un algoritmo un risultato, rispetto alla dimensione di il suo input. In pratica, è il file tasso di crescita nel numero di operazioni necessario per produrre un risultato per ogni unità aggiuntiva di input.

Nel primo articolo di questa serie, ho descritto un straight forward algoritmo di sommatoria. Per calcolare il somma di tutti i numeri tra i numeri p e q, Ho dichiarato un'altra variabile, re impostalo su zero. Ho poi aggiunto p per r, poi ho aggiunto p + 1 per r, poi p + 2e così via finché non ho finalmente aggiunto q stesso a r, a quel punto mi sono fermato e ho restituito il risultato, r, che ha tenuto il somma.

Quante operazioni richiederà, senza sapere quale sarà la dimensione di input finale, utilizzando solo le variabili astratte p e q? Quello che stiamo effettivamente facendo è eseguire un file ciclo continuo dove ogni iterazione aumenta p esattamente 1 e lo aggiunge r. Questo è in realtà l'aspetto del nostro algoritmo quando presentato in modo un po 'più formale:

1. lascia r = 0
2. while p è <= per q
3. r=p+r
4. p = p+1
5. ritorno r

Quando è disposto in questo modo in ciò che chiamiamo pseudocodice, diventa molto più facile vedere quante operazioni saranno necessarie. Scendi i passaggi numero per numero e conta le operazioni. La prima è un'istruzione, quindi è un'unica operazione. La seconda riga, tuttavia, è diversa. Cicli come questo si ripetono fino a quando la condizione non è soddisfatta, in questo caso, una volta p è più grande di q. Allora sappiamo che stiamo includendo q e p nel somma, quindi il numero di iterazioni attraverso questo ciclo continuo è uguale a q - (p - 1), qual è dimensione di input per il nostro algoritmo.

Ma questo è solo il numero di volte che iteriamo attraverso il ciclo, dobbiamo anche contare le operazioni al suo interno, che è dove aggiungiamo p e r e assegnare il risultato a r e poi aggiungiamo p e 1 e quindi assegnare il risultato a p. Quindi ci esibiamo due operazioni per ogni iterazione, e ci sono q - (p - 1)iterazioni. Tutto quello che dobbiamo fare ora è moltiplicare 2 operazioni e q - (p - 1)iterazioni ottenere 2 * (q - (p - 1)) operazioni per l'intero ciclo. Aggiungi le operazioni in 1. e 5., che ci dà un conteggio finale di 2 * (q - (p - 1)) + 2 operazioni per questo algoritmo.

Questa è una funzione lineare poiché non ci sono esponenti, quindi il tasso di crescita per il nostro algoritmo di somma è direttamente legato a il ingresso dimensione, che chiamiamo complessità temporale lineare. Come regola generale, qualunque sia il termine di ordine più alto in una formula che definisce la nostra complessità temporale è ciò che caratterizza la sua crescita nel tempo, quindi prendiamo il termine di ordine più alto e scarta il resto, lasciando q - (p - 1), che faremo chiamata n per semplicità.

La complessità del tempo lineare potrebbe sembrare inefficiente quando l'immagine ha dimensioni di input dell'ordine di miliardi, ma il tempo lineare non è poi così male. Possiamo fare di meglio però.

Sappiamo da molto tempo che il file somma di tuttii numeri a partire dal 1 e q è dato dalla formula (q * (q + 1)) / 2. Sappiamo anche che il fileproprietà commutativa dell'addizione ci dice che il risultato di (p-1 * (p)) / 2 sottratto da (q * (q + 1)) / 2 semplicemente ritaglia la parte della somma che include tutto da 1 per p-1, lasciando il somma dei numeri da p per q dietro, che è esattamente quello che vogliamo.

Questo algoritmo, a seconda di come è codificato, non dovrebbe richiedere più di tre operazioni. Poiché le operazioni matematiche dirette come questa sono esattamente le cose che i computer fanno meglio degli umani, potremmo unire le formule insieme in un'unica espressione matematica e il processore la masticherà facilmente come farebbe se la suddividessimo in blocchi più piccoli, ma ci atteniamo tre operazioni per il momento.

1. p = (p-1 * (p)) / 2
2. q
= (q * (q + 1)) / 2
3. ritorno ( q -p )

No loop, solo un numero costante di operazioni che non cambiano, indipendentemente dalla differenza tra p e q è. Questo algoritmo richiederà sempre tre operazioni per essere eseguito, quindi lo chiamiamo complessità temporale costante.

Ora, se non sapessi qual è il tuo dimensione di input sarebbe stato quando stavi progettando un algoritmo, quale algoritmo utilizzerai tra questi due? Ovviamente, il il secondo, perché algoritmi a tempo costante sono essenzialmente a pranzo libero computazionale per quanto riguarda l'input. Così come noi aumentare il nostro programma da gestire più dati, il loro tempo di esecuzione non cambierà in modo apprezzabile, mentre sappiamo che il nostro primo algoritmo crescerà esattamente quanto il nostro input, che potrebbe essere un valore di miliardi o più. Ovviamente, la complessità temporale costante non significa sempre che sia più efficiente, ma in questo caso è quello che vogliamo.

Prima che ci sedessimo a scrivere un file riga di codice, abbiamo già capito quale algoritmo fosse l'opzione migliore per il nostro contributo, e non abbiamo mai dovuto eseguirlo per scoprire come funziona. Questo è il motivo per cui usiamo complessità temporale, semplicemente non ci sono molti strumenti là fuori che siano altrettanto efficaci valutazione dell'efficienza degli algoritmi.

Cos'è la notazione Big O?

Abbiamo un modo speciale di annotare questa efficienza per rendere le cose più facili, qualcosa che chiamiamo Notazione O grande. In poche parole, Notazione O grande rappresenta il algoritmoefficienza correre attraverso il suo nella peggiore delle ipotesi. Se dovessi cercare un nome in una directory leggendo ogni nome finché non trovi quello giusto, lo scenario peggiore è che il nome che desideri è l'ultima voce nella directory. Ciò significa che dovresti leggere l'intera directory di n nomi per arrivare a quello che desideri. Quindi diciamo che questo algoritmo è O (n), dove n è il termine di ordine più alto nella nostra formula operativa.

Ci sono altri Notazioni importanti per il caso migliore e caso medio, ma ciò che conta davvero è il nella peggiore delle ipotesi; quelli sono quelli che possono mandare in crash il tuo computer o, peggio, la tua auto o il tuo aereo. Vanno dritti al cuore del perché complessità temporale è importante e indica perché alcuni algoritmi semplicemente non può risolvere un problema senza prendere pochi miliardi di anni per farlo.

Quindi come lo usiamo Notazione O grande? Il grafico sopra mostra come questi differiscono Notazioni Big O guarda in pratica, con il asse x essendo il tuo input e il tuo asse y il tempo impiegato per finire. Per maggiori dettagli, troverai un breve elenco di tutti i file Notazioni Big O che importa per ora e il complessità temporale loro rappresentano:

* O (1): Complessità temporale costante- Questo è il passaggio libero effettivamente computazionale di cui abbiamo parlato prima. Questo non significa necessariamente che sia più veloce. Significa solo che il file complessità temporale non è correlato alla dimensione dell'input.

* O (log n): Complessità temporale logaritmica- Questi sono più comuni quando si utilizza un file strategia divide et impera su un set di dati, dove ogni operazione scarta una grande porzione dell'input che ha escluso come non avente la soluzione. L'esempio classico è cercare una parola in un dizionario: apri a caso, controlla in quale sezione di lettere ti trovi, quindi ignora la parte in cui sai che la tua parola non sarà e suddividi e scartando ricorsivamente le sezioni rimanenti finché non trovi la tua parola.

* Sopra): Complessità temporale lineare- Questo era il nostro algoritmo di somma dall'inizio.

* O (n log n): Complessità temporale lineare- L'esecuzione di una trasformata di Fourier veloce è un O (n Log n) algoritmo, così come un Mergesort.

* Sopra2): Complessità temporale quadratica- Questo di solito si trova ogni volta che hai loop nidificati. Nel nostro primo algoritmo, se avessimo un secondo ciclo all'interno del primo, la funzione avrebbe sviluppato una complessità temporale quadratica.

* Soprac, c> 1): Complessità temporale polinomiale- Complessità temporale polinomiale è molto importante perché più o meno rappresenta il limite superiore su cosa a computer classico può risolvere in una quantità pratica di tempo.

* O (cn, n> 1, c> 1): Complessità temporale esponenziale- Qui è dove inizi a ottenere il file Algoritmi di miliardi di anni. Ogni volta che a unità di input ti fa il doppio del numero di operazioni eseguite rispetto al numero che vengono eseguiti se l'ingresso èn-1, hai complessità temporale esponenziale. L'esempio più comune che la maggior parte delle persone usa sta cercando di enumerare ogni possibile sottoinsieme di un insieme, ma Brute-forcing un Chiave di crittografia a 128 bit di solito è inserito in questa categoria.

* Sopra!): Complessità temporale fattoriale- Questi sono algoritmi che potrebbero probabilmente funzionare fino alla morte termica dell'Universo con una dimensione di input moderatamente grande di poche migliaia. Ogni volta che hai qualcosa come "in quanti modi diversi puoi organizzare questa sequenza", hai un problema di permutazione e la forza bruta verso una risposta richiede la creazione n! valori diversi, che è dato dal risultato di: n * (n - 1) * (n - 2) * ... * 3 * 2 * 1. Questi sono gli algoritmi che vengono eseguiti quasi parallelamente al file asse y nel diagramma sopra.

Perché non possiamo solo inventare algoritmi migliori

Non è per mancanza di tentativi. L'intero campo di informatica teorica è tutto nel cercare di trovare il massimo algoritmo efficiente per un determinato problema, ma a volte semplicemente non conosciamo la matematica. E non solo io e te, stiamo parlando di vincitori di medaglie Field che hanno dovuto affrontare problemi come il O (2n) e Sopra!) e la loro ipotesi è buona quanto la nostra.

C'è un intero catalogo di problemi che non abbiamo ancora la matematica da risolvere - ne parleremo più verso la fine della serie -, ma questi problemi agiscono come punti di strozzatura che creano inefficienze nel mondo degli affari, nella ricerca scientifica e in altri aree amministrative e ci sono molte persone che aspettano che questi problemi siano finalmente risolti. Sono stati persino offerti premi molto redditizi a chiunque sia in grado di risolvere alcune di queste cose, ma finora nessuno è stato in grado di farlo e alcuni di questi problemi sono rimasti in sospeso per decenni.

La ragione per cui computer classici non è in grado di risolvere questi problemi in modo efficiente né è integrato nei circuiti della macchina; ogni istruzione fornita deve essere completata prima di poter iniziare con quella successiva. I sistemi multicore o le macchine multiprocessore possono velocizzare le cose, ma probabilmente ne avresti ancora bisogno uno o due trilioni di anni per ottenere un risultato dopo aver unito tutti i nostri processori e averli liberati su un file Sopra!) problema dove n era qualcosa di simile 500.

Gli ingegneri informatici lo hanno visto arrivare per decenni, ma ora stiamo finalmente arrivando alla fine della linea per ciò che possiamo spremere da un computer classico. Semplicemente non puoi farli le operazioni vanno più velocie per natura possono farlo eseguire solo un'operazione alla volta. Se hai un algoritmo che richiede quintilioni di operazioni per completare, a computer classico deve eseguire tutti questi operazioni in ordine. A quel punto, il tempo necessario per ottenere un risultato diventa semplicemente una questione di matematica e fisica. Se vogliamo risolvere questi problemi che hanno complessità temporale esponenziale o maggiore, poi qualcos'altro è necessario.

La buona notizia è che sappiamo che è possibile, in almeno un caso, per trovare un algoritmo sufficientemente efficiente per trovare la risposta a uno di questi O (2n) problemi in complessità temporale polinomiale. Se può essere fatto una volta, allora è possibile farlo di nuovo; ci vuole solo eludere l'intera faccenda della "fisica".

Il quarto articolo della nostra serie su algoritmi e calcolo, In che modo l'algoritmo di Peter Shor condanna la crittografia RSA al fallimento, può essere trovato qui.


Guarda il video: Come è fatto lo SPAZIO-TEMPO? (Potrebbe 2022).


Commenti:

  1. Vozragore

    Informazione preziosa

  2. Oenomaus

    Penso di sbagliare. Sono in grado di dimostrarlo. Scrivimi in PM, parla.

  3. Theon

    Che frase necessaria... l'idea fenomenale, magnifica

  4. Luzige

    Hai torto. Mi sono assicurato. Suggerisco di discuterne.

  5. Robert

    Ti stai sbagliando. Scrivimi in PM.

  6. Aldin

    Secondo me non hai ragione. Discutiamone. Scrivimi in PM.

  7. Mooguhn

    Tutto su uno e così infinito

  8. Yakov

    Tutti i messaggi personali escono oggi?



Scrivi un messaggio