APA ITU EFISIENSI ALGOTIMA?
Analisa yang paling sering dilakukan pada suatu algoritma adalah waktu proses. Menentukan waktu proses secara tepat merupakan pekerjaan yang sangat sulit karena waktu proses secata eksak sangat terhgantung pada implementasi algoritma dan perangkat keras yang dipakai. Analisa yang di inginkan untuk menyatakan efisiensi algoritma haruslah dibuat se umum mungkin sehingga bias dipakai pada semua algoritma, terlepas dari implementasi dan juga compiler yang di pakai maupun perangkat keras yang digunakan. Akbiatnya analisa tidak dipakai pada waktu proses secata eksak. Kompleksitas algoritma cukup di nyatakan dalam order waktu proses (Big-Oh) secara fungsi jumlah data masukan yang diberikan. Dalam analisa tersebut kita menfokuskan diri pada operasi aktif yang merupakan pusat algoritma, yaitu bagian algoritma yang paling sering di eksekusi. Bagian-bagian lain seperti pemasukan data,penugasan (asigment), dan lain-lain dapat diabaikan karena bagian-bagian tersebut tidak sesering operasi aktif. Jumlah eksekusi operasi aktif itulah yang selanjutnya dihitung
KOMPLEKSITAS ALGORITMA
Sebuah pertanyaan yang sering muncul adalah
“Seberapa efisienkah suatu algoritma atau potongan kode?” Efisiensi tergantung dari beberapa
hal, diantaranya:
· Kinerja CPU
· Kinerja Memori
· Kinerja Disk
· Kinerja Jaringan
Semua aspek tersebut sangat penting, tapi
makalah ini akan membahas mengenai poin
pertama, yaitu CPU. Berhati-hatilah ketika
membandingkan antara
1. Performa: Berapa banyak waktu /
memori / disk yang digunakan ketika
program berjalan. Tergantung dari
mesin, compiler, dan kode.
2. Kompleksitas: Apa yang akan terjadi
ketika ukuran masalah semakin besar.
Kompleksitas memengaruhi performa, namun tidak sebaliknya. Waktu yang diperlukan untuk
melakukan suatu baris kode / algoritma
sebanding dengan operasi dasar yang dilakukan.
Beberapa contoh operasi dasar :
· Satu operasi aritmatika (misal: +, *)
· Satu assignment
· Satu ekspresi (misal: x==0)
· Pembacaan input
· Penulisan output (primitif)Beberapa algoritma melakukan jumlah operasi
yang sama dalam setiap kali pemanggilannya..
Algoritma seperti ini dikatakan memerlukan
waktu yang konstan.
Beberapa algoritma lain melakukan jumlah
operasi yang berbeda, tergantung dari jumlah
masukan pada parameter-nya. Misalnya,
algoritma pemanggilan berurutan (sequence),
jumlah operasi yang dilakukan tergantung dari
jumlah pemanggilan. Parameter yang nilainya
memengaruhi jumlah operasi yang dilakukan
disebut problem size atau input size.
Ketika kita mengukur kompleksitas suatu
algoritma, kita bukan memerlukan jumlah
operasi yang tepat, kita memerlukan bagaimana
hubungan antara jumlah operasi tersebut dengan
ukuran masalah (problem size). Jika problem
size-nya double, apakah jumlah operasi akan
tetap dua kali lipat? Ataukah bekembang dengan
cara tertentu? Untuk algoritma yang memerlukan
waktu yang konstan, melipatgandakan ukuran
masalah tidak memengaruhi jumlah operasi yang
dilakukan.
Lebih jauh lagi, biasanya kita tertarik dengan
worst case, atau kasus terburuk; yaitu jumlah
operasi terbanyak yang mungkin dilakukan
sebuah algoritma untuk ukuran masalah yang
diberikan (selain itu, terdapat juga kasus rata-rata
–average case- dan kasus terbaik –best case-)
MODEL PERHITUNGAN KEBUTUHAN WAKTU/RUANG
Waktu/Ruang
• Kita dapat mengukur waktu yang diperlukan oleh sebuah
algoritma dengan menghitung banyaknya
operasi/instruksi yang dieksekusi.
• Jika kita mengetahui besaran waktu (dalam satuan detik)
untuk melaksanakan sebuah operasi tertentu, maka kita
dapat menghitung berapa waktu sesungguhnya untuk
melaksanakan algoritma tersebut.
>>> Tipe data yang digunakan adalah :
- integer
- real
- real
Dua nilai yang sama dengan operator yang sama tetapi dengan variabel yang berbeda, maka terdapat perbedaan kecepatan / proses penyelesaiannya.
Contoh :
250 + 17 = 267 (lebih cepat dari)
250.0 + 17.0 = 0.25*103 + 0.17*102
= 0.25*103 + 0.017*103
= (0.25+ 0.017)*103
= 0.267*103
= 267.0
250 + 17 = 267 (lebih cepat dari)
250.0 + 17.0 = 0.25*103 + 0.17*102
= 0.25*103 + 0.017*103
= (0.25+ 0.017)*103
= 0.267*103
= 267.0
sumber:
Tidak ada komentar:
Posting Komentar