Perbandingan Kinerja Metode Iteratif dan Metode Rekursif dalam Algoritma Binary Search

Erba Lutfina, Fachrian Luthfi Ramadhan

Abstract


Penelitian ini membahas metode dan algoritma yang biasa digunakan dalam proses pencarian. Metode dan algoritma yang dibahas dalam paper ini adalah algoritma binary search dengan metode Rekursif dan metode iteratif. Pada masing-masing algoritma akan diberikan contoh program dalam bahasa pemrograman Python agar bisa memberi sedikit gambaran tentang implementasinya. Setiap algoritma akan dianalisis untuk mengetahui metode mana yang menghasilkan kompleksitas notasi big-O, penggunaan memori dan waktu akses yang paling efektif. Dari penelitian ini diketahui bahwa metode iteratif memiliki hasil yang lebih baik daripada metode rekursif. Hal ini dibuktikan dengan hasil waktu eksekusi metode rekursif sebesar  1.0601 s, 1.414 s, 4.515 s serta 51.4 MiB, 400.4 MiB, 3884.3 MiB untuk penggunaan memori, sedangkan algoritma iteratif hanya membutuhkan 0.0102 s, 0.0106 s, 0.0584 s untuk waktu eksekusi dan penggunaan memori berjumlah 44.3 MiB, 323.5 MiB, 3116.2 MiB.


Full Text:

PDF

References


D. Roy and A. Kundu, “A Comparative Analysis of Three Different Types of Searching Algorithms in Data Structure,†vol. 3, no. 5, pp. 6626–6630, 2014.

R. Mccauley, B. Hanks, S. Fitzgerald, and L. Murphy, “Recursion vs . Iteration : An Empirical Study of Comprehension Revisited,†pp. 350–355, 2015.

V. P. Parmar, “Comparing Linear Search and Binary Search Algorithms to Search an Element from a Linear List Implemented through Static Array , Dynamic Array and Linked List,†vol. 121, no. 3, pp. 13–17, 2015.

C. Mirolo, “Is Iteration Really Easier to Learn than Recursion for CS1 Students ?,†pp. 99–104, 2012.

M. D. Martins, I. P. Martins, and W. T. Fitch, “A novel approach to investigate recursion and iteration in visual hierarchical processing,†2015.

O. Kaser, “Analyzing Code with Θ , O and Ω,†pp. 1–18, 2016.

D. Mihhailov, V. Sklyarov, and A. Sudnitson, “Parallel FPGA-based Implementation of Recursive Sorting Algorithms,†pp. 121–126, 2010.

S. Grissom, L. Murphy, and S. Fitzgerald, “Paper vs . Computer-based Exams : A Study of Errors in Recursive Binary Tree Algorithms,†pp. 6–11, 2016.

M. Drmota and W. Szpankowski, “A Master Theorem for Discrete Divide and Conquer Recurrences,†vol. V, pp. 1–52.


Article Metrics

Abstract view : 1530 times
PDF - 5188 times

Refbacks

  • There are currently no refbacks.


SEMNASTIK 2019 diselenggarakan oleh : 

 Â