Kompleksitas Waktu dan Effisiensi Algoritma
Pada suatu algoritma yang perlu kita ketahui pada umumnya adalah:
- Space, yaitu alokasi yang bersifat sintetis.
- Struktur Program, berhubungan dengan berapa banyak langkah yang diperlukan untuk menjalankan algoritma yang dibuat
- Rekursif, pemakaian fungsi rekursif atau perulangan pada suatu algoritma.
Kompleksitas waktu pada sebuah algoritma berisi jumlah langkah dan ekspresi bilangan yang dibutuhkan sebagai fungsi dari ukuran permasalahan. Kompleksitas ruang berkaitan dengan sistem memori yang dibutuhkan untuk eksekusi sebuah program. Tabel di bawah memperlihatkan kelompok algoritma berdasarkan kompleksitas waktu asimptotiknya.
Efisiensi waktu algoritma
efisiensi waktu algoritma diukur dalam satuan n (problem size). terdapat 4 langkah untuk menentukan ukuran efisiensi waktu, antara lain:
- Menentukan problem size (n)
- Menentukan operasi dominan
- Menentukan Fungsi langkah → g(n)
- Menentukan kompleksitas waktu O(f(n)) (Big Oh function)
Menentukan Problem Size (n)
Menetukan Operasi Dominan
operasi dominan merupakan operasi yang paling banyak dilakukan, sesuai konteks permasalahan. misalkan pada algoritma menentukan nilai max/ min, operasi dominannya adalah operasi perbandingan ">" atau "<". pada algoritma searching operasi dominannya adalah operasi "=".
Menentukan Fungsi Langkah → g(n)
Menentukan kompleksitas waktu O(f(n)) (Big Oh function)
contoh:
tentukan g(n) dan Big Oh function dari algoritma di bawah ini:
k=n
while k> 0 do begin
for i=1 to n do
if(x>0) then ...
k=k div 2
end
Jawab: g(n) = n log n + 1 → O (n log n)
Contoh Kasus 1 Efisiensi Algoritma
Analisa
- Bagian (a) di eksekusi 1 kali
- Bagian (b) merupakan suatu loop, yang didasarkan atas kenaikan harga i dari i=1 hingga i=n. jadi statemen s=s+1 akan diproses sebanyak n kali sesuai kenaikan harga i
- Bagian (c) akan diproses 1 kali
- Karena bagian (b) merupakan bagian yang paling sering diproses, maka bagian (b) merupakan operasi aktif, sedangkan bagian (a) dan (c) dapat diabaikan karena jarang diproses.
- Bagian (b) diproses sama dengan banyak data yang di masukkan (n).
- Maka Algoritma penjumlahan bilangan rill tersebut mempunyai order sebanding dengan n atau memiliki Big Oh function = n atau O(n).
Contoh Kasus 2 (Belajar Kompleksitas Percabangan dan Looping dulu)
Contoh Kasus 3 (Belajar Kompleksitas Percabangan, Looping, Looping bersarang dulu)
Kompleksitas Waktu dan Effisiensi Algoritma
MARKIJAR: MARi KIta belaJAR
Posting Komentar untuk "Kompleksitas Waktu dan Effisiensi Algoritma"