Category Archives: Senza categoria

Complessità degli ordinamenti

Confrontiamo la complessità in tempo degli algoritmi di ordinamento ingenui con quella degli algoritmi evoluti, al variare della dimensione del problema

n n2 (ingenuo) nlog2n (evoluto) evoluto / ingenuo
103 106 ~104 10-2
106 1012 ~2*107 2*10-5
109 1018 ~3*1010 3*10-8
1010 1020 ~3,3*1011 3,3*10-9

Moltiplicando per 103 il numero di elementi nel vettore, si moltiplica per 106 il numero di operazioni dell’algoritmo ingenuo (per ~104 il numero di operazioni dell’algoritmo evoluto…).

Se un calcolatore svolge 106 operazioni elementari al secondo allora i tempi di attesa sono

n n2 nlog2n
103 ~1 sec ~0.01 sec
106 ~11,5 giorni ~20 sec
109 ~30 mila anni ~8 ore
1010 ~3 milioni di anni ~4 giorni

Se un calcolatore svolgerà, fra qualche anno, 109 operazioni elementari al secondo allora i tempi di attesa saranno

n n2 nlog2n
103 ~0.001 sec ~0.00001 sec
106 ~17 min ~0.02 sec
109 ~30 anni ~30 sec
1010 ~3000 anni ~5,5 min

Complessità: ricerca sequenziale

Analisi della complessità, in tempo e asintotica, dell’algoritmo di ricerca sequenziale. Il codice analizzato è il seguente

presenta operazioni di

  • assegnamento: 1, 5, 8, 9
  • confronto: 2, 4, 7
  • aritmetico-logiche: 3, 6

Il tempo totale richiesto da questo sottoprogramma alla CPU è

T = T1+(T2+T3+T4+T5+T6)*x+(T2+T3+T4)+T7+T8|9

con

  • (T2+T3+T4+T5+T6), le operazioni svolte ad ogni passo del While
  • x, il numero di volte che viene eseguito il While (da 0 a n)
  • (T2+T3+T4), quando K viene individuato alla posizione i-esima oppure il vettore finisce
  • T8|9, una delle due istruzioni finali

Per semplificare i calcoli si decide di trascurare le differenze esistenti tra i tempi di esecuzione delle diverse operazioni e di stabilire un tempo costante per tutte, allora

T = 6+5x

I valori effettivi di T sono

  • vettore vuoto: T1+(T2+T3+T4)+T7+T8 = 6
  • elemento in 1° posizione: T1+(T2+T3+T4)+T7+T9 = 6
  • elemento in 2° posizione: T1+[T2+T3+T4+T5+T6]+(T2+T3+T4)+T7+T9 = 6+5*1 = 11
  • elemento in 3° posizione: T1+[T2+T3+T4+T5+T6]*2+ … = 6+5*2 = 16
  • elemento in ultima posizione: 6+5*(n-1)
  • elemento non presente: 6+5n

Analizziamo i casi più interessanti

  • Caso ottimo, quando il vettore è vuoto oppure l’elemento K compare in 1° posizione: T=6
  • Caso pessimo, se l’elemento K non è presente: T=6+5n
  • Caso medio, supponiamo di effettuare n ricerche con l’elemento presente alle diverse posizioni: T=3.5+2.5n

Conclusioni

Il tempo richiesto è, tranne che nei casi banali, una funzione lineare di n, il numero di elementi presenti nel vettore

T(n)=c1+c2n

I valori delle due costanti c1 e c2 sono modesti e comunque poco significativi.


I calcoli per il caso medio

T=[(6+5*0)+(6+5*1)+(6+5*2)+...+(6+5(n-1))]/n
=[6n+5(1+2+...+n-1)]/n
=[6n+5(n-1)*n/2]/n
=6+5(n-1)/2
=6+5/2*n-5/2
=7/2+5/2*n
=3.5+2.5*n

Osserva che
1+2+...n=n(n+1)/2

Operatori condizionali

Uso Descrizione
> op1 è maggiore di op2?
>=
op1 è maggiore di o uguale a op2?
<
op1 è minore di op2?
<=
op1 è minore o uguale a op2?
==
op1 e op2 sono uguali?
!=
op1 e op2 non sono uguali?

Caratteri

Codice UNICODE

Classe #byte #bit Intervallo
char 2 16 ‘\u0000’
‘\uffff’

Sequenze di escape

Sono le sequenze di due caratteri, utilizzate per utilizzare caratteri non visualizzabili dall’editor

\\ backslash barra rovesciata
\? question mark punto di domanda
\’ single quote virgolette singole
\” double quote virgolette doppie
\b backspace spazio indietro
\n new line nuova linea
\r carriage return ritorno carrello
\t tab tabulazione

java.util.Scanner

Uno scanner di testo introdotto nella versione 5.0 per facilitare l’I/O testuale

Funziona con stringhe, file … e accetta delimitatori diversi (anche espressioni regolari…).

Costruttori

Metodi

boolean
byte
short
int
long
float
double
String
BigDecimal
BigInteger