Nazhifa Naura Yasmin, Lailatul Sofia, Arum Rahma Putri Sabrina, Adhystha Az-Zahra Putri, Imam Prayogo Pujiono

Interpolation Searching Algorithm Vs Algoritma Pencarian Tradisional: Analisis Efisiensi Memori dan Waktu Komputasi

Introduction

Interpolation searching algorithm vs algoritma pencarian tradisional: analisis efisiensi memori dan waktu komputasi. Bandingkan efisiensi memori & waktu komputasi Interpolation, Sequential, dan Binary Search di C++. Temukan algoritma pencarian optimal berdasarkan ukuran & pola data untuk kinerja terbaik.

Abstract

Penelitian ini bertujuan untuk membandingkan efisiensi memori dan waktu komputasi tiga algoritma pencarian: Sequential Search, Binary Search, dan Interpolation Search dalam bahasa C++. Pengujian dilakukan pada dataset terurut tanpa duplikasi sebanyak 100, 1.000, dan 10.000 data. Hasil menunjukkan Sequential Search paling hemat memori dengan rata-rata 12 byte pada semua dataset. Binary Search mencatat konsumsi memori tertinggi, terutama pada data besar (112 byte). Dari sisi waktu komputasi, Interpolation Search unggul pada dataset sedang (0,011 detik), sedangkan Sequential Search lebih cepat pada dataset kecil dan besar (0,019 dan 0,018 detik). Binary Search menunjukkan waktu komputasi paling tinggi (hingga 0,040 detik). Hasil ini menunjukkan bahwa pemilihan algoritma perlu mempertimbangkan ukuran dan pola distribusi data untuk mencapai efisiensi optimal.

Review

The study "Interpolation Searching Algorithm Vs Algoritma Pencarian Tradisional: Analisis Efisiensi Memori dan Waktu Komputasi" presents a comparative analysis of three fundamental search algorithms: Sequential Search, Binary Search, and Interpolation Search. Implemented in C++, the research meticulously evaluates their memory efficiency and computational time on sorted, unique datasets of varying sizes (100, 1,000, and 10,000 elements). The paper's objective to provide practical insights into algorithm selection based on empirical performance is relevant and valuable for developers and educators alike, reinforcing the understanding that theoretical Big-O complexity does not always translate directly to real-world performance across all scales. The abstract highlights several intriguing findings. Regarding memory consumption, Sequential Search emerged as the most efficient, consistently using a minimal 12 bytes across all datasets, while Binary Search consumed the most, peaking at 112 bytes for larger data. In terms of computation time, the results were less straightforward: Interpolation Search excelled on medium-sized datasets (0.011 seconds), yet Sequential Search surprisingly outperformed it on both small and large datasets (0.019 and 0.018 seconds, respectively). Binary Search consistently recorded the highest computation times, reaching up to 0.040 seconds. These results underscore the authors' concluding remark that optimal algorithm selection necessitates a careful consideration of data size and characteristics, moving beyond generalized assumptions. While the empirical comparison offers practical insights, the abstract raises several questions that warrant further clarification for a comprehensive understanding. The reported memory consumptions, measured in mere bytes, are unusually low and require a detailed explanation of what precisely was measured (e.g., algorithm state, auxiliary variables, or a broader system footprint) and how these differences arise in C++. More critically, the finding that Sequential Search is faster than both Binary and Interpolation Search on larger datasets contradicts conventional theoretical expectations (O(n) vs. O(log n) or O(log log n)). This necessitates a deeper investigation into the experimental setup, hardware specifics, caching effects, or constant factors that might explain this anomaly. Future work could benefit from analyzing data distribution's impact on Interpolation Search, expanding the dataset sizes to observe asymptotic behavior, and providing a more detailed breakdown of the experimental environment and methodology to ensure reproducibility and validate these counter-intuitive results.

Full Text

Comments

You need to be logged in to post a comment.