 |  | |
|
| | |
|
| |
ARCHIVI SEQUENZIALI:
Gli archivi sequenziali possono essere ordinati o non ordinati rispetto ad una chiave di riferimento.
Gli archivi sequenziali vengono di solito utilizzati per archivi costituiti da pochi record, poiche' per archivi di grandi dimensioni il tempo di ricerca diventa eccessivamente lungo.
Ipotizziamo di avere un archivio costituito da N record.
DEF. RECORD LOGICO: si definisce record logico la struttura di riferimento di uno specifico archivio, cioe' il formato in byte del tracciato record.
DEF.RECORD FISICO: si definisce record fisico la quantita' di memoria di massa trasferibile in memoria centrale con una sola operazione di lettura/scrittura (tale record fisico puo' contenere uno o piu' record logici). Un record fisico viene anche indicato con il termine pagina o blocco logico. Di solito una pagina e' dell'ordine di 2k Byte o di 4k Byte.
TEMPI DI COMPUTAZIONE DEGLI ARCHIVI SEQUENZIALI:
Il tempo di computazione o ordine di computazione si indica con O(N) e rappresenta il numero di confronti fra la chiave di riferimento (variabile di appoggio) e il valore della chiave dell'archivio.
Variabile appoggio FILE-DATI
CHIAVE
1
2
3
N
IPOTESI:
- Consideriamo un archivio con N Record
- Consideriamo il RECORD FISICO corrispondente al RECORD LOGICO e sviluppiamo la seguente
tabella:
TABELLA DI RICERCA CON O SENZA SUCCESSO PER GLI ARCHIVI SEQUENZIALI:
|
TIPI DI ARCHIVI |
RICERCA OTTIMA |
RICERCA MEDIA |
RICERCA PEGGIORE |
RICERCA SENZA SUCCESSO |
|
Archivi Sequenziali non ordinati |
O(1) |
O((N+1)/2) |
O(N) |
O(N+1) |
|
Archivi sequenziali ordinati |
O(1) |
O(Log(N)/2) |
O(Log(N)) |
O(Log(N)+1) |
NOTA:
Con Log(N) si intende logaritmo in base 2.
Per gli archivi ordinati si effettua la ricerca binaria o dicotomica.
ok
|
Privacy |
Articolo informazione
Commentare questo articolo:Non sei registratoDevi essere registrato per commentare ISCRIVITI |
Copiare il codice nella pagina web del tuo sito. |
Copyright InfTub.com 2025
