Description

Tujuan

Program ini dibuat untuk memenuhi beberapa tujuan berikut:

1. Mengimplementasikan perhitungan FPB dan KPK dengan pendekatan algoritmik yang berbeda, yaitu rekursif dan iteratif.
2. Mengukur efisiensi waktu eksekusi algoritma dengan teknik benchmarking.
3. Membandingkan performa algoritma rekursif dan iteratif dalam hal efisiensi waktu dan memori.
4. Memberikan pemahaman tentang konsep Big O dalam desain algoritma yang lebih efisien.

Desain Program

Program ini memiliki empat bagian utama, yaitu:

1. Algoritma FPB

Metode Rekursif: Menggunakan algoritma Euclidean yang diimplementasikan dengan pemanggilan fungsi secara rekursif. Prinsipnya adalah membagi dua angka dengan mengambil sisa bagi hingga salah satu angka menjadi nol. Kompleksitas waktu: O(log(min(a, b))).

Metode Iteratif: Algoritma Euclidean diimplementasikan menggunakan loop sehingga mengurangi overhead pemanggilan fungsi berulang. Kompleksitas waktu: O(log(min(a, b))).

2. Algoritma KPK

• KPK dihitung menggunakan rumus: KPK(a,b)=∣a×b∣FPB(a,b) ext{KPK}(a, b) = rac{|a imes b|}{ ext{FPB}(a, b)}KPK(a,b)=FPB(a,b)∣a×b∣​ Algoritma ini memanfaatkan hasil perhitungan FPB untuk menghitung KPK. Oleh karena itu, efisiensi algoritma KPK tergantung pada efisiensi algoritma FPB.

3. Benchmarking

• Menggunakan fungsi benchmark untuk mencatat waktu eksekusi setiap algoritma. Waktu awal dan akhir dicatat menggunakan fungsi time.time().

4. Kompleksitas Big O

• Kompleksitas FPB Rekursif: O(log(min(a, b))).
• Kompleksitas FPB Iteratif: O(log(min(a, b))).
• Kompleksitas KPK: Bergantung pada hasil FPB, sehingga memiliki kompleksitas yang sama dengan FPB.

Kode Program

Berikut adalah kode lengkap program Python:

import time

import math

def fpb_recursive(a, b):

if b == 0:

return a

return fpb_recursive(b, a % b)

def fpb_iterative(a, b):

while b != 0:

a, b = b, a % b

return a

def kpk(a, b):

return abs(a * b) // fpb_iterative(a, b)

def benchmark(func, *args):

start_time = time.time()

result = func(*args)

end_time = time.time()

execution_time = end_time - start_time

return result, execution_time

if __name__ == "__main__":

print("Program Perhitungan FPB dan KPK dengan Analisis Efisiensi Algoritma")

print("------------------------------------------------------------")

num1 = int(input("Masukkan bilangan pertama: "))

num2 = int(input("Masukkan bilangan kedua: "))

fpb_result, fpb_time = benchmark(fpb_recursive, num1, num2)

print(f"FPB (Rekursif) antara {num1} dan {num2} adalah {fpb_result} (Waktu: {fpb_time:.10f} detik)")

fpb_iter_result, fpb_iter_time = benchmark(fpb_iterative, num1, num2)

print(f"FPB (Iteratif) antara {num1} dan {num2} adalah {fpb_iter_result} (Waktu: {fpb_iter_time:.10f} detik)")

kpk_result, kpk_time = benchmark(kpk, num1, num2)

print(f"KPK antara {num1} dan {num2} adalah {kpk_result} (Waktu: {kpk_time:.10f} detik)")

print(" Perbandingan Waktu Eksekusi:")

print(f"- FPB Rekursif: {fpb_time:.10f} detik")

print(f"- FPB Iteratif: {fpb_iter_time:.10f} detik")

print(f"- KPK: {kpk_time:.10f} detik")

Output

Kesimpulan

Efisiensi FPB Rekursif vs Iteratif:

• Algoritma iteratif lebih cepat dibandingkan dengan algoritma rekursif karena tidak memiliki overhead pemanggilan fungsi berulang.

KPK:

• KPK sangat bergantung pada efisiensi algoritma FPB.

Rekomendasi:

• Untuk kasus sederhana, pendekatan iteratif lebih direkomendasikan karena waktu eksekusi lebih kecil dan konsumsi memori lebih rendah.