IRIS Institutional Research Information System - AIR Archivio Istituzionale della Ricerca
IRIS è il sistema di gestione integrata dei dati della ricerca (persone, progetti, pubblicazioni, attività) adottato dall'Università degli Studi di Milano.
AIR nasce in UNIMI nel 2006 con lo scopo di raccogliere, documentare e conservare le informazioni sulla produzione scientifica dell'Università degli Studi di Milano e costituisce di fatto l'Anagrafe della ricerca dell'Ateneo.
EnglishWe revisit the classical algorithms for searching over sorted sets and introduce a new algorithm, called adaptive search, that combines the good features of Interpolation search and those of Binary search. W.r.t. Insertion sort, only a constant number of extra comparisons is introduced. Yet, under several relevant input data distributions our algorithm shows average case cost comparable to that of Interpolation Search, i.e., O(log log n) while the worst case cost is always in O(log n), as with Binary search. This result compares well with the traditional result of Santoro and Sidney Interpolation-Binary Search and the recent approach of Demaine et al. on searching non-independent data.
| Titolo: | Flexible interpolated-binary search over sorted sets |
| Autori: | PAGANO, FRANCESCO (Secondo) PROVETTI, ALESSANDRO (Ultimo) |
| Data di pubblicazione: | set-2009 |
| Parole Chiave: | sorting ; sorted-sets |
| Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
| Enti collegati al convegno: | Politecnico di Milano |
| Tipologia: | Conference Object |
| Citazione: | Flexible interpolated-binary search over sorted sets / B. Bonasera, F. Pagano, A. Provetti. ((Intervento presentato al convegno Italian Conference on Theoretical Computer Science (ICTCS) tenutosi a Cremona nel 2009. |
| Appare nelle tipologie: | 14 - Intervento a convegno non pubblicato |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| ictcs2009.pdf | Publisher's version/PDF | Open Access Visualizza/Apri |
Copyright © 2019