Supponete di dover memorizzare una matrice quadrata con N righe e N colonne di numeri interi diversi fra loro (con N <= 10), e di poterlo fare o usando un array a due dimensioni con 10×10 componenti di tipo int sia per le righe che per le colonne, oppure utilizzando una lista, in cui ogni nodo contiene tre interi (i valori degli indici di riga e colonna e il valore dell’elemento dell’array) e un puntatore al prossimo nodo.
Assumendo che sia un int che un puntatore occupino ciascuno 4 byte, qual è il massimo valore di N per cui l’uso della lista risulta conveniente in termini di memoria occupata (cioè, il massimo valore di N per cui la lista occupa strettamente meno byte dell’array)?
Soluzione: 24.
Osserva
- 10*10 int occupano 100*4 byte = 400 byte
- un nodo della lista occupa 4*4 byte = 16 byte
mentre la lista
- 1*16 byte = 16 byte
- 2*16 byte = 32 byte
- …
- 24*16 byte = 384 byte
- 25*16 byte = 400 byte
- 26*16 byte = 416 byte
- …