Dovendo giudicare una parte di codice di programmazione quali criteri adotteresti?
 | Complessità in tempo |
| complessità in spazio |
| leggibilità |
| correttezza |
| interfaccia utente. |
Il problema “Individuare il valore minimo in un vettore” che complessità ha? Lineare: O(n), è necessario scorrere tutto il vettore per individuare il valore minimo
E se il vettore è ordinato? Costante: O(1), il minimo occupa la prima posizione (V[1]!!!)
Stabilisci una classifica per le prestazioni degli algoritmi con complessità in tempo
n=8 | n "molto" grande | |||
T1(n)=20n+10 | 20*8+10=170 | 2° | O(n) | 2° |
T2(n)=2n2 | 2*64=128 | 1° | O(n2) | 4° |
T3(n)=200+n | 200+8=208 | 3° | O(n) | 2° |
T4(n)=2n2+100n | 2*64+100*8=928 | 6° | O(n2) | 4° |
T5(n)=20log2n+300 | 20*3+300=360 | 5° | O(log2n) | 1° |
T6(n)=10log2n+n2+20n | 10*3+64+20*8=254 | 4° | O(n2) | 4° |
Inserisci le cifre della tua data di nascita nel vettore V[-, -, -, -, -, -] e poi analizza il codice seguente
Procedure YYYY(Var V: Vettore; N: Integer);Begin if(N > 0) then begin writeln(V[N]); YYYY(V, N-1); end;End;YYYY(V, 6);
| Come si comporta? 1°: YYYY(V, 6) scrive V[6] e chiama ... 2°: YYYY(V, 5) scrive V[5] e chiama ... ... 6°: YYYY(V, 1) scrive V[1] e chiama... 7°: YYYY(V, 0) che ritorna senza ulteriori chiamate ricorsive. |
| Cosa visualizza? Il contenuto del vettore al contrario |
| Quanto tempo impiega? Ci sono ~4 operazioni elementari (N>0, write, N-1, chiamata) per 6 volte e 1 (N>0) alla fine quindi ~25 |
| Quanto tempo impiega al variare del parametro N? T(n)=4n+1, quindi asintoticamente O(n) |
Analizza il codice seguente
Function XXXX(N, R: LongInt): LongInt;Begin if(N < 2) then XXXX:=R Else XXXX:=XXXX(N-2, R+1);End;Write(XXXX(10, 0));
| Come si comporta? 1°: XXXX(10, 0) chiama ... 2°: XXXX( 8, 1) chiama ... 3°: XXXX( 6, 2) chiama ... 4°: XXXX( 4, 3) chiama ... 5°: XXXX( 2, 4) chiama ... 6°: XXXX( 0, 5) restituisce 5 |
| Cosa visualizza? Il valore 5, cioè il quoziente della divisione intera per 2 di N |
| Quanto tempo impiega? Ci sono ~4 operazioni elementari (N<2, N-2, R+1, :=) per 5 volte e 2 (N<2, :=) alla fine quindi ~22 |
| Quanto tempo impiega al variare del parametro N? T(n)=4(n div 2)+2~2n+2, quindi asintoticamente O(n) |