Interpolación una vez búsqueda binaria sobre una lista ordenada
Autores: Lin, Jun-Lin
Idioma: Inglés
Editor: MDPI
Año: 2024
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
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.
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.