La versione più recente è stata modificata il 2006-03-07 22:07:58 da GaS
Aggiunzioni:
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn^2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n^2), si legge “ordine di n^2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n) ≤ cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Omissioni:
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn^2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n^2), si legge “ordine di n^2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n) ≤ cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Modificato il 2006-03-07 22:07:29 da GaS
Aggiunzioni:
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn^2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n^2), si legge “ordine di n^2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n) ≤ cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Omissioni:
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn^2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n^2), si legge “ordine di n^2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n) ≤ cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Modificato il 2006-03-07 22:06:42 da GaS
Aggiunzioni:
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn^2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n^2), si legge “ordine di n^2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n) ≤ cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Omissioni:
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n^2), si legge “ordine di n^2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n) ≤ cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Modificato il 2006-03-07 22:04:58 da GaS
Aggiunzioni:
Supponiamo di avere cinque algoritmi A_1-A_5 con le seguenti complessità di tempo:
La complessità di tempo rappresentata è il numero delle unità di tempo richieste per processare un input di taglia n. Assumendo che un'unità di tempo equivale ad un millisecondo, l'algoritmo A_1 può processare in un secondo un input di taglia 1000, laddove l'algoritmo A_5 può processare in un secondo un input di taglia massima 9. La figura 1.1 dà la taglia dei problemi che possono essere risolti in un secondo, un minuto e un ora da ognuno dei cinque algoritmi.
Supponiamo che la prossima generazione di computer sia dieci volte più veloce di quella corrente. La figura 1.2 mostra l'incremento nella taglia del problema che si può risolvere, si può notare che con l'algoritmo A_3 la taglia è più del triplo.
Invece di un incremento di velocità, consideriamo l'effetto prodotto dall'utilizzo di un algoritmo più efficiente. Osserviamo nuovamente la Fig. 1.1. Usando un minuto come base per il confronto, sostituendo l'algoritmo A_4 con A_3 possiamo risolvere un problema di taglia sei volte più grande; sostituendo l'algoritmo A_4 con A_2 possiamo risolvere un problema di taglia 125 volte più grande. Questi risultati sono di gran lunga più impressionanti dell'incremento doppio ottenuto dalla decuplicazione della velocità. Se utilizziamo come base per il confronto un'ora, le differenze sono ancora più significative. Concludiamo che la complessità asintotica di un algoritmo è un'importante misura della bontà dell'algoritmo, e promette di diventare sempre più importante con le future velocità dei computer.
Non concentrandoci sulla performance in ordine di grandezza, possiamo meglio comprendere che un algoritmo con un rapido tasso di crescita può avere una costante di proporzionalità minore di un algoritmo con un minore tasso di crescita. In questo caso, l'algoritmo con un tasso di crescita più rapido risulta essere migliore per problemi con piccola taglia, possibilmente per tutti quei problemi che possono interessarci. Per esempio, supponiamo la complessità di tempo degli algoritmi A_1 , A_2 , A_3 , A_4 e A_5 siano realmente 1000n, 100n log n, 10 n^2, n^3 e 2^n. Allora A_5 sarebbe il migliore per problemi di taglia 2 ≤ n ≤ 9, A_3 sarebbe il migliore per 10 ≤ n ≤ 58, A_2 sarebbe il migliore per 59 ≤ n ≤ 1024, e A_1 sarebbe il migliore per problemi di taglia maggiore di 1024.
Omissioni:
Supponiamo di avere cinque algoritmi A1-A5 con le seguenti complessità di tempo:
La complessità di tempo rappresentata è il numero delle unità di tempo richieste per processare un input di taglia n. Assumendo che un'unità di tempo equivale ad un millisecondo, l'algoritmo A1 può processare in un secondo un input di taglia 1000, laddove l'algoritmo A5 può processare in un secondo un input di taglia massima 9. La figura 1.1 dà la taglia dei problemi che possono essere risolti in un secondo, un minuto e un ora da ognuno dei cinque algoritmi.
Supponiamo che la prossima generazione di computer sia dieci volte più veloce di quella corrente. La figura 1.2 mostra l'incremento nella taglia del problema che si può risolvere, si può notare che con l'algoritmo A3 la taglia è più del triplo.
Invece di un incremento di velocità, consideriamo l'effetto prodotto dall'utilizzo di un algoritmo più efficiente. Osserviamo nuovamente la Fig. 1.1. Usando un minuto come base per il confronto, sostituendo l'algoritmo A4 con A3 possiamo risolvere un problema di taglia sei volte più grande; sostituendo l'algoritmo A4 con A2 possiamo risolvere un problema di taglia 125 volte più grande. Questi risultati sono di gran lunga più impressionanti dell'incremento doppio ottenuto dalla decuplicazione della velocità. Se utilizziamo come base per il confronto un'ora, le differenze sono ancora più significative. Concludiamo che la complessità asintotica di un algoritmo è un'importante misura della bontà dell'algoritmo, e promette di diventare sempre più importante con le future velocità dei computer.
Non concentrandoci sulla performance in ordine di grandezza, possiamo meglio comprendere che un algoritmo con un rapido tasso di crescita può avere una costante di proporzionalità minore di un algoritmo con un minore tasso di crescita. In questo caso, l'algoritmo con un tasso di crescita più rapido risulta essere migliore per problemi con piccola taglia, possibilmente per tutti quei problemi che possono interessarci. Per esempio, supponiamo la complessità di tempo degli algoritmi A_1, A_2, A_3, A_4 e A_5 siano realmente 1000n, 100n log n, 10 n^2, n^3 e 2^n. Allora A5 sarebbe il migliore per problemi di taglia 2 ≤ n ≤ 9, A3 sarebbe il migliore per 10 ≤ n ≤ 58, A2 sarebbe il migliore per 59 ≤ n ≤ 1024, e A1 sarebbe il migliore per problemi di taglia maggiore di 1024.
Modificato il 2006-03-07 22:00:29 da GaS
Aggiunzioni:
Nel descrivere e comunicare algoritmi ci piacerebbe una notazione più naturale e semplice da comprendere che un programma ad accesso random, un programma memorizzato ad accesso random, o una macchina di Turing. Per questa ragione introdurremo anche un linguaggio ad alto livello chiamato Pidgin ALGOL. Utilizzeremo tale linguaggio per descrivere gli algoritmi. Tuttavia, per capire la complessità computazionale di un algoritmo descritto in Pidgin ALGOL dobbiamo riferire quest'ultimo a modelli più formali.
Omissioni:
Nel descrivere e comunicare algoritmi ci piacerebbe una notazione più naturale e semplice da comprendere che un programma ad accesso random, un programma memorizzato ad accesso random, o una macchina di Turing. Per questa ragione introdurremo anche un linguaggio ad alto livello chiamato Pidgin ALGOL. Utilizzeremo tale linguaggio in tutto il libro per descrivere gli algoritmi. Tuttavia, per capire la complessità computazionale di un algoritmo descritto in Pidgin ALGOL dobbiamo riferire quest'ultimo a modelli più formali.
Modificato il 2006-03-07 07:47:03 da GaS
Aggiunzioni:
Non concentrandoci sulla performance in ordine di grandezza, possiamo meglio comprendere che un algoritmo con un rapido tasso di crescita può avere una costante di proporzionalità minore di un algoritmo con un minore tasso di crescita. In questo caso, l'algoritmo con un tasso di crescita più rapido risulta essere migliore per problemi con piccola taglia, possibilmente per tutti quei problemi che possono interessarci. Per esempio, supponiamo la complessità di tempo degli algoritmi A_1, A_2, A_3, A_4 e A_5 siano realmente 1000n, 100n log n, 10 n^2, n^3 e 2^n. Allora A5 sarebbe il migliore per problemi di taglia 2 ≤ n ≤ 9, A3 sarebbe il migliore per 10 ≤ n ≤ 58, A2 sarebbe il migliore per 59 ≤ n ≤ 1024, e A1 sarebbe il migliore per problemi di taglia maggiore di 1024.
Omissioni:
Non concentrandoci sulla performance in ordine di grandezza, possiamo meglio comprendere che un algoritmo con un rapido tasso di crescita può avere una costante di proporzionalità minore di un algoritmo con un minore tasso di crescita. In questo caso, l'algoritmo con un tasso di crescita più rapido risulta essere migliore per problemi con piccola taglia, possibilmente per tutti quei problemi che possono interessarci. Per esempio, supponiamo la complessità di tempo degli algoritmi A1, A2, A3, A4 e A5 siano realmente 1000n, 100n log n, 10 n^2, n^3 e 2^n. Allora A5 sarebbe il migliore per problemi di taglia 2 ≤ n ≤ 9, A3 sarebbe il migliore per 10 ≤ n ≤ 58, A2 sarebbe il migliore per 59 ≤ n ≤ 1024, e A1 sarebbe il migliore per problemi di taglia maggiore di 1024.
Modificato il 2006-03-06 23:25:13 da GaS
Aggiunzioni:
Omissioni:
Modificato il 2006-03-06 23:20:43 da GaS
Aggiunzioni:
Il tempo richiesto da un algoritmo espresso come funzione della taglia di un problema è chiamato complessità di tempo dell'algoritmo. Il comportamento limite della complessità come incremento della taglia è chiamato complessità asintotica di tempo. Analoghe definizioni possono essere date per la complessità di spazio e la complessità asintotica dello spazio. È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n^2), si legge “ordine di n^2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n) ≤ cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Omissioni:
Il tempo richiesto da un algoritmo espresso come funzione della taglia di un problema è chiamato complessità di tempo dell'algoritmo. Il comportamento limite della complessità come incremento della taglia è chiamato complessità asintotica di tempo. Analoghe definizioni possono essere date per la complessità di spazio e la complessità asintotica dello spazio.
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n2), si legge “ordine di n^2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n)<=cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Modificato il 2006-03-06 23:18:48 da GaS
Aggiunzioni:
Torna ad Algoritmi e Strutture dati
Omissioni:
Torna a Algoritmi e Strutture dati
Modificato il 2006-03-06 23:17:37 da GaS
Aggiunzioni:
Omissioni:
Modificato il 2006-03-06 23:16:56 da GaS
Aggiunzioni:
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n2), si legge “ordine di n^2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n)<=cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Supponiamo di avere cinque algoritmi A1-A5 con le seguenti complessità di tempo:
(† Se non espressamente definito, tutti i logaritmi sono in base 2)
Non concentrandoci sulla performance in ordine di grandezza, possiamo meglio comprendere che un algoritmo con un rapido tasso di crescita può avere una costante di proporzionalità minore di un algoritmo con un minore tasso di crescita. In questo caso, l'algoritmo con un tasso di crescita più rapido risulta essere migliore per problemi con piccola taglia, possibilmente per tutti quei problemi che possono interessarci. Per esempio, supponiamo la complessità di tempo degli algoritmi A1, A2, A3, A4 e A5 siano realmente 1000n, 100n log n, 10 n^2, n^3 e 2^n. Allora A5 sarebbe il migliore per problemi di taglia 2 ≤ n ≤ 9, A3 sarebbe il migliore per 10 ≤ n ≤ 58, A2 sarebbe il migliore per 59 ≤ n ≤ 1024, e A1 sarebbe il migliore per problemi di taglia maggiore di 1024.
Omissioni:
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n2), si legge “ordine di n2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n)<=cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Supponiamo di avere cinque algoritmi A_1-A_5 con le seguenti complessità di tempo:
(† Se non espressamente definito, tutti i logaritmi sono in base 2)
Non concentrandoci sulla performance in ordine di grandezza, possiamo meglio comprendere che un algoritmo con un rapido tasso di crescita può avere una costante di proporzionalità minore di un algoritmo con un minore tasso di crescita. In questo caso, l'algoritmo con un tasso di crescita più rapido risulta essere migliore per problemi con piccola taglia, possibilmente per tutti quei problemi che possono interessarci. Per esempio, supponiamo la complessità di tempo degli algoritmi A1, A2, A3, A4 e A5 siano realmente 1000n, 100n log n, 10 n2, n3 e 2n. Allora A5 sarebbe il migliore per problemi di taglia 2 ≤ n ≤ 9, A3 sarebbe il migliore per 10 ≤ n ≤ 58, A2 sarebbe il migliore per 59 ≤ n ≤ 1024, e A1 sarebbe il migliore per problemi di taglia maggiore di 1024.
Modificato il 2006-03-06 23:14:14 da GaS
Aggiunzioni:
Invece di un incremento di velocità, consideriamo l'effetto prodotto dall'utilizzo di un algoritmo più efficiente. Osserviamo nuovamente la Fig. 1.1. Usando un minuto come base per il confronto, sostituendo l'algoritmo A4 con A3 possiamo risolvere un problema di taglia sei volte più grande; sostituendo l'algoritmo A4 con A2 possiamo risolvere un problema di taglia 125 volte più grande. Questi risultati sono di gran lunga più impressionanti dell'incremento doppio ottenuto dalla decuplicazione della velocità. Se utilizziamo come base per il confronto un'ora, le differenze sono ancora più significative. Concludiamo che la complessità asintotica di un algoritmo è un'importante misura della bontà dell'algoritmo, e promette di diventare sempre più importante con le future velocità dei computer.
Non concentrandoci sulla performance in ordine di grandezza, possiamo meglio comprendere che un algoritmo con un rapido tasso di crescita può avere una costante di proporzionalità minore di un algoritmo con un minore tasso di crescita. In questo caso, l'algoritmo con un tasso di crescita più rapido risulta essere migliore per problemi con piccola taglia, possibilmente per tutti quei problemi che possono interessarci. Per esempio, supponiamo la complessità di tempo degli algoritmi A1, A2, A3, A4 e A5 siano realmente 1000n, 100n log n, 10 n2, n3 e 2n. Allora A5 sarebbe il migliore per problemi di taglia 2 ≤ n ≤ 9, A3 sarebbe il migliore per 10 ≤ n ≤ 58, A2 sarebbe il migliore per 59 ≤ n ≤ 1024, e A1 sarebbe il migliore per problemi di taglia maggiore di 1024.
Prima di procedere con la nostra discussione sugli algoritmi e la loro complessità, dobbiamo specificare un modello di dispositivo di calcolo per eseguire gli algoritmi e definire cosa si intende per passo base della computazione. Sfortunatamente non esiste un modello di computazione universale. Una delle maggiori difficoltà sorge dalla dimensione delle stringhe dei computer. Per esempio, se si assume che una stringa di computer può contenere un intero di dimensione arbitraria, allora un intero problema potrebbe essere codificato in un'unica stringa di computer. Dall'altra parte, se si assume che la stringa sia finita, si deve considerare la difficoltà nel memorizzare semplicemente interi di grandezza arbitraria, allo stesso modo di altri problemi che uno spesso evita quando tratta di modeste dimensioni. Per ogni problema dobbiamo selezionare un modello appropriato che possa accuratamente riflettere il tempo di computazione attuale su un reale computer.
Nella seguente sezione discutiamo diversi modelli fondamentali di dispositivi di calcolo, i più importanti dei quali sono le macchine ad accesso random (Random Access Machine), i programmi memorizzati ad accesso random (Random Access Stored Program Machine) e la macchina di Turing (Turing Machine). Questi tre modelli sono equivalenti come potenza computazionale ma non in velocità.
Forse la motivazione più importante per modelli formali di computazione è il desiderio di scoprire l'inerente difficoltà computazionale dei vari problemi. Cercheremo di raggiungere i limiti inferiori di computazione di tempo. Nell'ordine di mostrare che non esistono algoritmi che possano dare risultati in un tempo minore a certi limiti, dobbiamo precisare e spesso a grandi linee la definizione di cosa costituisce un algoritmo. Le macchine di Turing sono un esempio di tale definizione.
Nel descrivere e comunicare algoritmi ci piacerebbe una notazione più naturale e semplice da comprendere che un programma ad accesso random, un programma memorizzato ad accesso random, o una macchina di Turing. Per questa ragione introdurremo anche un linguaggio ad alto livello chiamato Pidgin ALGOL. Utilizzeremo tale linguaggio in tutto il libro per descrivere gli algoritmi. Tuttavia, per capire la complessità computazionale di un algoritmo descritto in Pidgin ALGOL dobbiamo riferire quest'ultimo a modelli più formali.
Omissioni:
Modificato il 2006-03-06 23:11:52 da GaS
Aggiunzioni:
(† Se non espressamente definito, tutti i logaritmi sono in base 2)
La complessità di tempo rappresentata è il numero delle unità di tempo richieste per processare un input di taglia n. Assumendo che un'unità di tempo equivale ad un millisecondo, l'algoritmo A1 può processare in un secondo un input di taglia 1000, laddove l'algoritmo A5 può processare in un secondo un input di taglia massima 9. La figura 1.1 dà la taglia dei problemi che possono essere risolti in un secondo, un minuto e un ora da ognuno dei cinque algoritmi.
Supponiamo che la prossima generazione di computer sia dieci volte più veloce di quella corrente. La figura 1.2 mostra l'incremento nella taglia del problema che si può risolvere, si può notare che con l'algoritmo A3 la taglia è più del triplo.
Modificato il 2006-03-06 23:06:39 da GaS
Aggiunzioni:
Omissioni:
Modificato il 2006-03-06 23:00:35 da GaS
Aggiunzioni:
Modificato il 2006-03-06 22:55:21 da GaS
Aggiunzioni:
Omissioni:
Modificato il 2006-03-06 22:53:58 da GaS
Aggiunzioni:
Omissioni:
Modificato il 2006-03-06 22:51:24 da GaS
Aggiunzioni:
Omissioni:
Torna a Algoritmi e Strutture dati
Modificato il 2006-03-06 22:50:20 da GaS
Aggiunzioni:
Torna a Algoritmi e Strutture dati
Omissioni:
Torna ad Algoritmi e Strutture dati
La versione più vecchia di questa pagina è stata modificata il 2006-03-06 22:48:11 da GaS []
Il tempo richiesto da un algoritmo espresso come funzione della taglia di un problema è chiamato complessità di tempo dell'algoritmo. Il comportamento limite della complessità come incremento della taglia è chiamato complessità asintotica di tempo. Analoghe definizioni possono essere date per la complessità di spazio e la complessità asintotica dello spazio.
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n2), si legge “ordine di n2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n)<=cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Si potrebbe sospettare che i tremendi progressi nella velocità di calcolo portato dall'avvento dei computer di ultima generazione possa sminuire l'importanza di algoritmi efficienti. Tuttavia è vero l'esatto contrario. Come i computer diventano più veloci e possiamo maneggiare problemi più grandi, è la complessità di un algoritmo che determina l'incremento nella taglia del problema che può essere archiviato con un incremento nella velocità del computer.
Supponiamo di avere cinque algoritmi A_1-A_5 con le seguenti complessità di tempo:
Torna ad Algoritmi e Strutture dati
Aggiunzioni:
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn^2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n^2), si legge “ordine di n^2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n) ≤ cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Omissioni:
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn^2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n^2), si legge “ordine di n^2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n) ≤ cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Modificato il 2006-03-07 22:07:29 da GaS
Aggiunzioni:
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn^2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n^2), si legge “ordine di n^2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n) ≤ cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Omissioni:
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn^2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n^2), si legge “ordine di n^2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n) ≤ cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Modificato il 2006-03-07 22:06:42 da GaS
Aggiunzioni:
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn^2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n^2), si legge “ordine di n^2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n) ≤ cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Omissioni:
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n^2), si legge “ordine di n^2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n) ≤ cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Modificato il 2006-03-07 22:04:58 da GaS
Aggiunzioni:
Supponiamo di avere cinque algoritmi A_1-A_5 con le seguenti complessità di tempo:
La complessità di tempo rappresentata è il numero delle unità di tempo richieste per processare un input di taglia n. Assumendo che un'unità di tempo equivale ad un millisecondo, l'algoritmo A_1 può processare in un secondo un input di taglia 1000, laddove l'algoritmo A_5 può processare in un secondo un input di taglia massima 9. La figura 1.1 dà la taglia dei problemi che possono essere risolti in un secondo, un minuto e un ora da ognuno dei cinque algoritmi.
Supponiamo che la prossima generazione di computer sia dieci volte più veloce di quella corrente. La figura 1.2 mostra l'incremento nella taglia del problema che si può risolvere, si può notare che con l'algoritmo A_3 la taglia è più del triplo.
Invece di un incremento di velocità, consideriamo l'effetto prodotto dall'utilizzo di un algoritmo più efficiente. Osserviamo nuovamente la Fig. 1.1. Usando un minuto come base per il confronto, sostituendo l'algoritmo A_4 con A_3 possiamo risolvere un problema di taglia sei volte più grande; sostituendo l'algoritmo A_4 con A_2 possiamo risolvere un problema di taglia 125 volte più grande. Questi risultati sono di gran lunga più impressionanti dell'incremento doppio ottenuto dalla decuplicazione della velocità. Se utilizziamo come base per il confronto un'ora, le differenze sono ancora più significative. Concludiamo che la complessità asintotica di un algoritmo è un'importante misura della bontà dell'algoritmo, e promette di diventare sempre più importante con le future velocità dei computer.
Non concentrandoci sulla performance in ordine di grandezza, possiamo meglio comprendere che un algoritmo con un rapido tasso di crescita può avere una costante di proporzionalità minore di un algoritmo con un minore tasso di crescita. In questo caso, l'algoritmo con un tasso di crescita più rapido risulta essere migliore per problemi con piccola taglia, possibilmente per tutti quei problemi che possono interessarci. Per esempio, supponiamo la complessità di tempo degli algoritmi A_1 , A_2 , A_3 , A_4 e A_5 siano realmente 1000n, 100n log n, 10 n^2, n^3 e 2^n. Allora A_5 sarebbe il migliore per problemi di taglia 2 ≤ n ≤ 9, A_3 sarebbe il migliore per 10 ≤ n ≤ 58, A_2 sarebbe il migliore per 59 ≤ n ≤ 1024, e A_1 sarebbe il migliore per problemi di taglia maggiore di 1024.
Omissioni:
Supponiamo di avere cinque algoritmi A1-A5 con le seguenti complessità di tempo:
La complessità di tempo rappresentata è il numero delle unità di tempo richieste per processare un input di taglia n. Assumendo che un'unità di tempo equivale ad un millisecondo, l'algoritmo A1 può processare in un secondo un input di taglia 1000, laddove l'algoritmo A5 può processare in un secondo un input di taglia massima 9. La figura 1.1 dà la taglia dei problemi che possono essere risolti in un secondo, un minuto e un ora da ognuno dei cinque algoritmi.
Supponiamo che la prossima generazione di computer sia dieci volte più veloce di quella corrente. La figura 1.2 mostra l'incremento nella taglia del problema che si può risolvere, si può notare che con l'algoritmo A3 la taglia è più del triplo.
Invece di un incremento di velocità, consideriamo l'effetto prodotto dall'utilizzo di un algoritmo più efficiente. Osserviamo nuovamente la Fig. 1.1. Usando un minuto come base per il confronto, sostituendo l'algoritmo A4 con A3 possiamo risolvere un problema di taglia sei volte più grande; sostituendo l'algoritmo A4 con A2 possiamo risolvere un problema di taglia 125 volte più grande. Questi risultati sono di gran lunga più impressionanti dell'incremento doppio ottenuto dalla decuplicazione della velocità. Se utilizziamo come base per il confronto un'ora, le differenze sono ancora più significative. Concludiamo che la complessità asintotica di un algoritmo è un'importante misura della bontà dell'algoritmo, e promette di diventare sempre più importante con le future velocità dei computer.
Non concentrandoci sulla performance in ordine di grandezza, possiamo meglio comprendere che un algoritmo con un rapido tasso di crescita può avere una costante di proporzionalità minore di un algoritmo con un minore tasso di crescita. In questo caso, l'algoritmo con un tasso di crescita più rapido risulta essere migliore per problemi con piccola taglia, possibilmente per tutti quei problemi che possono interessarci. Per esempio, supponiamo la complessità di tempo degli algoritmi A_1, A_2, A_3, A_4 e A_5 siano realmente 1000n, 100n log n, 10 n^2, n^3 e 2^n. Allora A5 sarebbe il migliore per problemi di taglia 2 ≤ n ≤ 9, A3 sarebbe il migliore per 10 ≤ n ≤ 58, A2 sarebbe il migliore per 59 ≤ n ≤ 1024, e A1 sarebbe il migliore per problemi di taglia maggiore di 1024.
Modificato il 2006-03-07 22:00:29 da GaS
Aggiunzioni:
Nel descrivere e comunicare algoritmi ci piacerebbe una notazione più naturale e semplice da comprendere che un programma ad accesso random, un programma memorizzato ad accesso random, o una macchina di Turing. Per questa ragione introdurremo anche un linguaggio ad alto livello chiamato Pidgin ALGOL. Utilizzeremo tale linguaggio per descrivere gli algoritmi. Tuttavia, per capire la complessità computazionale di un algoritmo descritto in Pidgin ALGOL dobbiamo riferire quest'ultimo a modelli più formali.
Omissioni:
Nel descrivere e comunicare algoritmi ci piacerebbe una notazione più naturale e semplice da comprendere che un programma ad accesso random, un programma memorizzato ad accesso random, o una macchina di Turing. Per questa ragione introdurremo anche un linguaggio ad alto livello chiamato Pidgin ALGOL. Utilizzeremo tale linguaggio in tutto il libro per descrivere gli algoritmi. Tuttavia, per capire la complessità computazionale di un algoritmo descritto in Pidgin ALGOL dobbiamo riferire quest'ultimo a modelli più formali.
Modificato il 2006-03-07 07:47:03 da GaS
Aggiunzioni:
Non concentrandoci sulla performance in ordine di grandezza, possiamo meglio comprendere che un algoritmo con un rapido tasso di crescita può avere una costante di proporzionalità minore di un algoritmo con un minore tasso di crescita. In questo caso, l'algoritmo con un tasso di crescita più rapido risulta essere migliore per problemi con piccola taglia, possibilmente per tutti quei problemi che possono interessarci. Per esempio, supponiamo la complessità di tempo degli algoritmi A_1, A_2, A_3, A_4 e A_5 siano realmente 1000n, 100n log n, 10 n^2, n^3 e 2^n. Allora A5 sarebbe il migliore per problemi di taglia 2 ≤ n ≤ 9, A3 sarebbe il migliore per 10 ≤ n ≤ 58, A2 sarebbe il migliore per 59 ≤ n ≤ 1024, e A1 sarebbe il migliore per problemi di taglia maggiore di 1024.
Omissioni:
Non concentrandoci sulla performance in ordine di grandezza, possiamo meglio comprendere che un algoritmo con un rapido tasso di crescita può avere una costante di proporzionalità minore di un algoritmo con un minore tasso di crescita. In questo caso, l'algoritmo con un tasso di crescita più rapido risulta essere migliore per problemi con piccola taglia, possibilmente per tutti quei problemi che possono interessarci. Per esempio, supponiamo la complessità di tempo degli algoritmi A1, A2, A3, A4 e A5 siano realmente 1000n, 100n log n, 10 n^2, n^3 e 2^n. Allora A5 sarebbe il migliore per problemi di taglia 2 ≤ n ≤ 9, A3 sarebbe il migliore per 10 ≤ n ≤ 58, A2 sarebbe il migliore per 59 ≤ n ≤ 1024, e A1 sarebbe il migliore per problemi di taglia maggiore di 1024.
Modificato il 2006-03-06 23:25:13 da GaS
Aggiunzioni:
1.1 Gli algoritmi e la loro complessità
Omissioni:
Gli algoritmi e la loro complessità
Modificato il 2006-03-06 23:20:43 da GaS
Aggiunzioni:
Il tempo richiesto da un algoritmo espresso come funzione della taglia di un problema è chiamato complessità di tempo dell'algoritmo. Il comportamento limite della complessità come incremento della taglia è chiamato complessità asintotica di tempo. Analoghe definizioni possono essere date per la complessità di spazio e la complessità asintotica dello spazio. È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n^2), si legge “ordine di n^2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n) ≤ cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Omissioni:
Il tempo richiesto da un algoritmo espresso come funzione della taglia di un problema è chiamato complessità di tempo dell'algoritmo. Il comportamento limite della complessità come incremento della taglia è chiamato complessità asintotica di tempo. Analoghe definizioni possono essere date per la complessità di spazio e la complessità asintotica dello spazio.
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n2), si legge “ordine di n^2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n)<=cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Modificato il 2006-03-06 23:18:48 da GaS
Aggiunzioni:
Torna ad Algoritmi e Strutture dati
Omissioni:
Torna a Algoritmi e Strutture dati
Modificato il 2006-03-06 23:17:37 da GaS
Aggiunzioni:
Omissioni:
Modificato il 2006-03-06 23:16:56 da GaS
Aggiunzioni:
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n2), si legge “ordine di n^2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n)<=cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Supponiamo di avere cinque algoritmi A1-A5 con le seguenti complessità di tempo:
(† Se non espressamente definito, tutti i logaritmi sono in base 2)
Non concentrandoci sulla performance in ordine di grandezza, possiamo meglio comprendere che un algoritmo con un rapido tasso di crescita può avere una costante di proporzionalità minore di un algoritmo con un minore tasso di crescita. In questo caso, l'algoritmo con un tasso di crescita più rapido risulta essere migliore per problemi con piccola taglia, possibilmente per tutti quei problemi che possono interessarci. Per esempio, supponiamo la complessità di tempo degli algoritmi A1, A2, A3, A4 e A5 siano realmente 1000n, 100n log n, 10 n^2, n^3 e 2^n. Allora A5 sarebbe il migliore per problemi di taglia 2 ≤ n ≤ 9, A3 sarebbe il migliore per 10 ≤ n ≤ 58, A2 sarebbe il migliore per 59 ≤ n ≤ 1024, e A1 sarebbe il migliore per problemi di taglia maggiore di 1024.
Omissioni:
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n2), si legge “ordine di n2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n)<=cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Supponiamo di avere cinque algoritmi A_1-A_5 con le seguenti complessità di tempo:
(† Se non espressamente definito, tutti i logaritmi sono in base 2)
Non concentrandoci sulla performance in ordine di grandezza, possiamo meglio comprendere che un algoritmo con un rapido tasso di crescita può avere una costante di proporzionalità minore di un algoritmo con un minore tasso di crescita. In questo caso, l'algoritmo con un tasso di crescita più rapido risulta essere migliore per problemi con piccola taglia, possibilmente per tutti quei problemi che possono interessarci. Per esempio, supponiamo la complessità di tempo degli algoritmi A1, A2, A3, A4 e A5 siano realmente 1000n, 100n log n, 10 n2, n3 e 2n. Allora A5 sarebbe il migliore per problemi di taglia 2 ≤ n ≤ 9, A3 sarebbe il migliore per 10 ≤ n ≤ 58, A2 sarebbe il migliore per 59 ≤ n ≤ 1024, e A1 sarebbe il migliore per problemi di taglia maggiore di 1024.
Modificato il 2006-03-06 23:14:14 da GaS
Aggiunzioni:
Non concentrandoci sulla performance in ordine di grandezza, possiamo meglio comprendere che un algoritmo con un rapido tasso di crescita può avere una costante di proporzionalità minore di un algoritmo con un minore tasso di crescita. In questo caso, l'algoritmo con un tasso di crescita più rapido risulta essere migliore per problemi con piccola taglia, possibilmente per tutti quei problemi che possono interessarci. Per esempio, supponiamo la complessità di tempo degli algoritmi A1, A2, A3, A4 e A5 siano realmente 1000n, 100n log n, 10 n2, n3 e 2n. Allora A5 sarebbe il migliore per problemi di taglia 2 ≤ n ≤ 9, A3 sarebbe il migliore per 10 ≤ n ≤ 58, A2 sarebbe il migliore per 59 ≤ n ≤ 1024, e A1 sarebbe il migliore per problemi di taglia maggiore di 1024.
Prima di procedere con la nostra discussione sugli algoritmi e la loro complessità, dobbiamo specificare un modello di dispositivo di calcolo per eseguire gli algoritmi e definire cosa si intende per passo base della computazione. Sfortunatamente non esiste un modello di computazione universale. Una delle maggiori difficoltà sorge dalla dimensione delle stringhe dei computer. Per esempio, se si assume che una stringa di computer può contenere un intero di dimensione arbitraria, allora un intero problema potrebbe essere codificato in un'unica stringa di computer. Dall'altra parte, se si assume che la stringa sia finita, si deve considerare la difficoltà nel memorizzare semplicemente interi di grandezza arbitraria, allo stesso modo di altri problemi che uno spesso evita quando tratta di modeste dimensioni. Per ogni problema dobbiamo selezionare un modello appropriato che possa accuratamente riflettere il tempo di computazione attuale su un reale computer.
Nella seguente sezione discutiamo diversi modelli fondamentali di dispositivi di calcolo, i più importanti dei quali sono le macchine ad accesso random (Random Access Machine), i programmi memorizzati ad accesso random (Random Access Stored Program Machine) e la macchina di Turing (Turing Machine). Questi tre modelli sono equivalenti come potenza computazionale ma non in velocità.
Forse la motivazione più importante per modelli formali di computazione è il desiderio di scoprire l'inerente difficoltà computazionale dei vari problemi. Cercheremo di raggiungere i limiti inferiori di computazione di tempo. Nell'ordine di mostrare che non esistono algoritmi che possano dare risultati in un tempo minore a certi limiti, dobbiamo precisare e spesso a grandi linee la definizione di cosa costituisce un algoritmo. Le macchine di Turing sono un esempio di tale definizione.
Nel descrivere e comunicare algoritmi ci piacerebbe una notazione più naturale e semplice da comprendere che un programma ad accesso random, un programma memorizzato ad accesso random, o una macchina di Turing. Per questa ragione introdurremo anche un linguaggio ad alto livello chiamato Pidgin ALGOL. Utilizzeremo tale linguaggio in tutto il libro per descrivere gli algoritmi. Tuttavia, per capire la complessità computazionale di un algoritmo descritto in Pidgin ALGOL dobbiamo riferire quest'ultimo a modelli più formali.
Omissioni:
Modificato il 2006-03-06 23:11:52 da GaS
Aggiunzioni:
(† Se non espressamente definito, tutti i logaritmi sono in base 2)
La complessità di tempo rappresentata è il numero delle unità di tempo richieste per processare un input di taglia n. Assumendo che un'unità di tempo equivale ad un millisecondo, l'algoritmo A1 può processare in un secondo un input di taglia 1000, laddove l'algoritmo A5 può processare in un secondo un input di taglia massima 9. La figura 1.1 dà la taglia dei problemi che possono essere risolti in un secondo, un minuto e un ora da ognuno dei cinque algoritmi.
Modificato il 2006-03-06 23:06:39 da GaS
Aggiunzioni:
Omissioni:
Modificato il 2006-03-06 23:00:35 da GaS
Aggiunzioni:
Modificato il 2006-03-06 22:55:21 da GaS
Aggiunzioni:
Gli algoritmi e la loro complessità
Omissioni:
Gli Algoritmi e la loro Complessità
Modificato il 2006-03-06 22:53:58 da GaS
Aggiunzioni:
Gli Algoritmi e la loro Complessità
Omissioni:
ALGORITMI E LORO COMPLESSITA'
Modificato il 2006-03-06 22:51:24 da GaS
Aggiunzioni:
ALGORITMI E LORO COMPLESSITA'
Torna a Algoritmi e Strutture datiOmissioni:
Torna a Algoritmi e Strutture dati
Modificato il 2006-03-06 22:50:20 da GaS
Aggiunzioni:
Torna a Algoritmi e Strutture dati
Omissioni:
Torna ad Algoritmi e Strutture dati
La versione più vecchia di questa pagina è stata modificata il 2006-03-06 22:48:11 da GaS []
Vista della pagina:
Gli algoritmi possono essere valutati tramite vari criteri. Molto spesso saremo interessati nel valutare la crescita del tempo e dello spazio richiesti alla risoluzione delle più grandi istanze di un problema. Dovremmo associare ad un problema un intero, chiamato taglia del problema, che è una misura della quantità dei dati in input. Per esempio, la taglia di un problema di moltiplicazione matriciale potrebbe essere la dimensione maggiore delle matrici da moltiplicare. La taglia di un problema sui grafi potrebbe essere il numero dei vertici.Il tempo richiesto da un algoritmo espresso come funzione della taglia di un problema è chiamato complessità di tempo dell'algoritmo. Il comportamento limite della complessità come incremento della taglia è chiamato complessità asintotica di tempo. Analoghe definizioni possono essere date per la complessità di spazio e la complessità asintotica dello spazio.
È la complessità asintotica di un algoritmo che alla fine determina la taglia dei problemi che possono essere risolti da un algoritmo. Se un algoritmo processa input di taglia n in un tempo cn2 per qualche costante c, allora diremo che la complessità di tempo di tale algoritmo è O(n2), si legge “ordine di n2”. Più precisamente, una funzione g(n) è detta O(f(n)) se esiste una costante c tale che g(n)<=cf(n) comunque preso n da un insieme finito di valori non negativi (al massimo vuoto).
Si potrebbe sospettare che i tremendi progressi nella velocità di calcolo portato dall'avvento dei computer di ultima generazione possa sminuire l'importanza di algoritmi efficienti. Tuttavia è vero l'esatto contrario. Come i computer diventano più veloci e possiamo maneggiare problemi più grandi, è la complessità di un algoritmo che determina l'incremento nella taglia del problema che può essere archiviato con un incremento nella velocità del computer.
Supponiamo di avere cinque algoritmi A_1-A_5 con le seguenti complessità di tempo:
Torna ad Algoritmi e Strutture dati
