performance algoritmi ricerca e inserimento

redcloud80

Utente Attivo
8
0
Salve. Ho la necessità di effettuare inserimenti e ricerche all'interno di un array. Se inserisco gli elementi a mano a mano ho una complessità di inserimento O(1) e una complessità O(n) in fase di ricerca. Per migliorare la ricerca potrei usare la ricerca binaria ma perderei quell'O(1) in fase di inserimento. Contando che effettuo molto più ricerche che inserimenti, mi conviene ottimizzare la ricerca (usando la ricerca binaria) effettuando però un ordinamento in fase di inserimento?
 

K.I.

Utente Èlite
1,644
7
CPU
Intel Prescott 530J con Zalman 7700CU
Scheda Madre
Asus P5GD2
HDD
Maxtor Sata 160Gb e Floppy
RAM
Micron 1024Mb
GPU
Asus 6600GT PCI-E
Audio
Onboard con Creative GD580
Monitor
HP F2105 e Scheda TV Terratec Cinergy 600TV
PSU
Enermax Noisetaker 485W
OS
Windowd XP e Kubuntu 7.04
Beh, se fai molte più ricerche è meglio ottimizzare quelle.

Se ci lavori molto, puoi comprare il libro algoritmi in C (visto che usi gli array) ti spiega i vari tipi di algoritmi (con codice già fatto), la complessita e per quali dimensioni conviene un algoritmo o un'altro, ecco l'indice del libro e i dati dell'autore.

Ciao!

Titolo Algoritmi in C: fondamenti, strutture dati, ordinamento, ricerca - terza edizione
Editore Addison Wesley
Autore Sedgewick Robert
Titolo originale Algorithms in C: Fundamentals, sorting, searching, and strings preliminary version, third edition, parts 1-4 (Addison Wesley)
Codice aw1518
Collana -
Pagine 713
Livello Intermedio Avanzato
Lingua Italiano
Pubbl. Novembre 2002


Questa nuova edizione italiana, traduzione della terza edizione del best-seller di Robert Sedgewick sugli algoritmi, conferma la validita' di un progetto che ha gia' riscosso un notevole successo con le edizioni precedenti. In questo caso, non si tratta pero' di una semplice revisione, poiche' le modifiche apportate a un impianto gia' valido sono numerose. La linea scelta e' stata quella dell'approfondimento di argomenti ormai "classici", associati a una presentazione di temi e idee derivate direttamente dalla ricerca effettuata in questi ultimi anni. Algoritmi in C offre una copertura attuale e completa dei piu' importanti algoritmi e strutture dati; presenta inoltre nuovi algoritmi, con spiegazioni dettagliate. I contenuti sono presentati attraverso concise implementazioni in C, in modo che il fruitore possa apprezzarne le proprieta' fondamentali e, al contempo, metterli alla prova su applicazioni reali.
Grazie al suo nuovo formato (195 x 260) e alle molte, innovative figure, il testo conserva la giusta miscela di teoria e pratica che ha reso l'opera di Sedgewick un best-seller per programmatori e professionisti, e una risorsa irrinunciabile per oltre 250.000 studenti.

Tra le novita' della nuova edizione:

* ampia trattazione di array, liste concatenate, stringhe, alberi, e delle altre principali strutture dati;
* maggiore enfasi sugli ADT, e oltre 100 algoritmi realtivi a: ordinamento, selezione, ADT coda con priorita', ADT tabella di simboli;
* nuove implementazioni relative a: code binomiali, ordinamento digitale a piu' vie, reti d'ordinamento di Batcher, alberi di ricerca binari randomizzati, alberi splay, e altro ancora;
* oltre 1000 nuovi esercizi e 100 nuove figure, per aiutare gli studenti ad apprendere meglio le proprieta' degli algoritmi.

Robert Sedgewick insegna al Dipartimento di Informatica dell'Universita' di princeton. Ha ottenuto il Ph.D. a Stanford con una dissertazione sul Quicksort sotto la supervisione di Donald E. Knuth. E' direttore di Adobe Systems e ha fatto parte dello staff di ricerca di Xerox PARC, INRIA e dell'Institute for Defense Analyses.

Indice

Fondamenti

Capitolo 1. Introduzione
1.1 Algoritmi
1.2 Un esempio: il problema della connettivita'
1.3 Algoritmi union-find
1.4 Prospettive
1.5 Sommario degli argomenti

Capitolo 2. Principi di progettazione degli algoritmi
2.1 Implementazione e analisi empiriche
2.2 Analisi degli algoritmi
2.3 Velocita' di crescita delle funzioni
2.4 Notazione O grande
2.5 Ricorrenze fondamentali
2.6 Esempio di analisi di algoritmi
2.7 Tempo garantito, tempo stimato e limitazioni

Strutture dati

Capitolo 3. Strutture dati elementari
3.1 Costrutti di base
3.2 Array
3.3 Liste concatenate
3.4 Elaborazione elementare di liste
3.5 Allocazione di memoria per liste
3.6 Stringhe
3.7 Strutture dati composte

Capitolo 4. Tipi di dati astratti
4.1 Oggetti astratti e collezioni di oggetti
4.2 Tipo di dato astratto stack
4.3 Esempi di client dell'ADT stack
4.4 Implementazione dell'ADT stack
4.5 Creazione di nuovi ADT
4.6 Code FIFO e code generalizzate
4.7 Elementi duplicati ed elementi indice
4.8 ADAT di prima categoria
4.9 Esempio di ADT basato su applicazioni
4.10 Prospettive

Capitolo 5. Ricorsione e alberi
5.1 Algoritmi ricorsivi
5.2 Divide et impera
5.3 Programmazione dinamica
5.4 Alberi
5.5 Proprieta' matematiche degli alberi binari
5.6 Attraversamento di alberi
5.7 Algoritmi ricorsivi su alberi binari
5.8 Attraversamento di grafi
5.9 Prospettive

Ordinamento

Capitolo 6. Metodi di ordinamento elementari
6.1 Regole del gioco
6.2 Ordinamento per selezione
6.3 Ordinamento per inserzione
6.4 Bubble sort
6.5 Prestazioni degli ordinamenti elementari
6.6 Shellsort
6.7 Ordinamento di altri tipi di dati
6.8 Ordinamento di indici e puntatori
6.9 Ordinamento di liste concatenate
6.10 Indicizzazione con chiavi

Capitolo 7. Quicksort
7.1 L'algoritmo di base
7.2 Descrizione delle prestazioni del Quicksort
7.3 Dimensione dello stack
7.4 File parziali di piccole dimensioni
7.5 Partizionamento dl metodo della mediana fra tre elementi
7.6 Chiavi duplicate
7.7 Stringhe e vettori
7.8 Selezione

Capitolo 8. Merging e Mergesort
8.1 Merging a due vie
8.2 Merging astratto sul posto
8.3 Mergesort top-down
8.4 Miglioramenti dell'algoritmo di base
8.5 Mergesort bottom-up
8.6 Descrizione delle prestazioni del Mergesort
8.7 Implementazione del Mergesort su liste concatenate
8.8 Rivisitazione della ricorsione

Capitolo 9. Code con priorita' e Heapsort
9.1 Implementazione elementari
9.2 La struttura dati heap
9.3 Algoritmi su heap
9.4 Heapsort
9.5 ADT coda con priorita'
9.6 Code con priorita' per elementi indice
9.7 Code binomiali

Capitolo 10. Ordinamento digitale
10.1 Bit, byte e parole
10.2 Quicksort binario
10.3 Ordinamento digitale
10.4 Quicksort digitale a tre vie
10.5 Ordinamento digitale LSD
10.6 Descrizione delle prestazioni degli ordinamenti digitali
10.7 Ordinamenti sublineari

Capitolo 11. Metodi speciali di ordinamento
11.1 Mergesort odd-even di batcher
11.2 Reti di ordinamento
11.3 Ordinamento esterno
11.4 Implementazioni del sort-merge
11.5 Sort-merge parallelo

Ricerca

Capitolo 12. Tabelle di simboli e alberi binari di ricerca
12.1 Tipo di dato astratto tabella di simboli
12.2 Ricerca indicizzata da chiave
12.3 Ricerca sequenziale
12.4 Ricerca binaria
12.5 Alberi binari di ricerca (BST)
12.6 Prestazioni dei BST
12.7 Implementazione con indici e tabelle di simboli
12.8 Inserimento alla radice in un BST
12.9 Implementazione tramite BST di altre funzioni

Capitolo 13. Alberi bilanciati
13.1 BST randomizzati
13.2 Splay BST
13.3 Alberi 2-3-4 top-down
13.4 Alberi red-black
13.5 Skip list
13.6 Studio delle prestazioni

Capitolo 14. Hashing
14.1 Funzioni di hash
14.2 Concatenazioni separate
14.3 Scansione lineare
14.4 Hashing doppio
14.5 Tabelle hash dinamiche
14.6 Prospettive

Capitolo 15. Ricerca digitale
15.1 Alberi di ricerca digitale
15.2 Trie
15.3 Trie praticia
15.4 Trie a piu' vie e TST
15.5 Algoritmi per indici di stringhe di testo

Capitolo 16. Ricerca esterna
16.1 Regole del gioco
16.2 Accesso sequenziale indicizzato
16.3 B alberi
16.4 Hashing estendibile
16.5 Prospettive

Indice analitico
 

Entra

oppure Accedi utilizzando
Discord Ufficiale Entra ora!

Discussioni Simili