logo móvil
Contáctanos

Interpolación una vez búsqueda binaria sobre una lista ordenada

Autores: Lin, Jun-Lin

Idioma: Inglés

Editor: MDPI

Año: 2024

Descargar PDF

Acceso abierto

Artículo científico
2024

Interpolación una vez búsqueda binaria sobre una lista ordenada


Categoría

Matemáticas

Subcategoría

Matemáticas generales

Palabras clave

Lista
Búsqueda binaria
Búsqueda por interpolación
Complejidad temporal
Híbridos
Costo de computación

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 21

Citaciones: Sin citaciones


Descripción
La búsqueda en una lista ordenada es un problema clásico en ciencias de la computación. La Búsqueda Binaria toma como máximo intentos para encontrar un elemento en una lista ordenada de tamaño . La Búsqueda por Interpolación logra una complejidad temporal promedio de para datos distribuidos uniformemente. También existen híbridos de Búsqueda Binaria y Búsqueda por Interpolación para manejar datos con distribuciones desconocidas. Este documento analiza el costo computacional de estos métodos y muestra que la interpolación puede afectar significativamente su rendimiento; por lo tanto, se propone un nuevo método, Búsqueda Binaria de Interpolación Única (IOBS). Los resultados experimentales muestran que IOBS supera a los híbridos de Búsqueda Binaria y Búsqueda por Interpolación para datos distribuidos de manera no uniforme.

Otros recursos que podrían interesarte

Temas Virtualpro