Perbandingan Kinerja Metode Iteratif dan Metode Rekursif dalam Algoritma Binary Search

Authors

  • Erba Lutfina Karangturi National University
  • Fachrian Luthfi Ramadhan Karangturi National University

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.

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.

Downloads

Published

2019-11-21

Issue

2019: Semnastik 2019

Section

Articles

License

Penulis yang mempublikasikan artikelnya dalam publikasi ini setuju dengan ketentuan berikut :


  1. Hak cipta tetap pada penulis dan memberikan hak kepada SEMNASTIK 2019 sebagai prioritas pertama untuk mempublikasikan artikelnya dengan lisensi Creative Commons Attribution License yang memperbolehkan artikel untuk dapat dibagikan dengan pengakuan terhadap penulis artikel dan SEMNASTIK 2019 sebagai tempat publikasinya.
  2. Penulis dapat mendistribusikan publikasi artikelnya secara non-eksklusif (contoh : pada repository universitas atau pada buku) dengan pemberitahuan atau pengakuan publikasi di SEMNASTIK 2019.
  3. Penulis diijinkan untuk mencantumkan karyanya secara online (misal : di website pribadi atau di repository universitas) sebelum dan sesudah proses pengiriman (lihat The Effect of Open Access).