Pada suatu algoritma yang perlu kita ketahui pada umumnya adalah:
- Space, yaitu alokasi yang bersifat sintetis.
- Struktur Program, berafiliasi dengan berapa banyak langkah yang dibutuhkan untuk menjalankan algoritma yang dibuat
- Rekursif, pemakaian fungsi rekursif atau perulangan pada suatu algoritma.
Kompleksitas waktu pada sebuah algoritma berisi jumlah langkah dan lisan bilangan yang dibutuhkan sebagai fungsi dari ukuran permasalahan. Kompleksitas ruang berkaitan dengan sistem memori yang dibutuhkan untuk sanksi sebuah program. Tabel di bawah menawarkan kelompok algoritma menurut kompleksitas waktu asimptotiknya.
Efisiensi waktu algoritma
efisiensi waktu algoritma diukur dalam satuan n (problem size). terdapat 4 langkah untuk memilih 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 mayoritas merupakan operasi yang paling banyak dilakukan, sesuai konteks permasalahan. misalkan pada algoritma memilih nilai max/ min, operasi dominannya yaitu operasi perbandingan ">" atau "<". pada algoritma searching operasi dominannya yaitu 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 sanksi 1 kali
- Bagian (b) merupakan suatu loop, yang didasarkan atas kenaikan harga i dari i=1 sampai i=n. jadi statemen s=s+1 akan diproses sebanyak n kali sesuai kenaikan harga i
- Bagian (c) akan diproses 1 kali
- Karena bab (b) merupakan bab yang paling sering diproses, maka bab (b) merupakan operasi aktif, sedangkan bab (a) dan (c) sanggup diabaikan alasannya yaitu 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