Algoritma adalah urutan atau tahapan-tahapan dan atau langkah-langkah untuk menyelesaikan masalah. Tahapan harus logis,terurut dan sistematis untuk menyelesaikan masalah.
Apabila sesuatu algoritma diberi untuk sesuatu masalah dan ditentukan sebagai betul, langkah seterusnya ialah menentukan jumlah sumber, seperti masa dan ruang, yang diperlukan oleh algoritma tersebut.
Langkah ini dikenali sebagai analisis algoritma.
Analisis yang dilakukan ke atas algoritma dari segi:
- Effectiveness
- Correctness
- Termination
- Efficiency
- Complexity
EFFECTIVENESS
Mudah dipahami sesuatu algoritma
Mudah dilakukan semakan(tracing), biarpun manual.
Langkah-langkah adalah tersusun atau organize.
CORRECTNESS
Algoritma yang dihasilkan akan mengeluarkan output yang diharapkan atau
dikehendaki dan betul.
TERMINATION
Langkah-langkah penyelesaian bagi algoritma mempunyai ‘terminator’ yang telah
ditentukan.
Termination atau pemberhentian akan berlaku seperti dirancang dan bukan disebabkan oleh masalah seperti looping dan out of memory atau unfinite value.
EFFICIENCY
Mengikur sejauh mana komputer menggunakan sumber yang diperlukan oleh algoritma.
COMPLEXITY
Satu analisis algoritma yang bersifat kualitatif.
Ia merujuk kepada kesukaran dalam perlaksanaan dan kesannya bagi satu algoritma.
Juga diukur dalam bentuk masa, iaitu masa yang sedikit diambil menggambarkan kurang kompleksitinya
Kriteria Algoritma yg baik
- Ada output
- Efektifitas dan Efisiensi
- Jumlah langkah berhingga
- Berakhir
- Terstruktur
1. Merencanakan suatu algoritma
Sebelum merepresentasikan suatu algoritma utk memperoleh solusi dari suatu masalah, ditentukan dahulu model penyelesaiannya. Ada banyak model utk menyelesaikan masalah. Tetapi ada satu model yang terbaik. Sehingga penguasaan teknik variasi disain atau model harus dikuasai sebaik-baiknya.
2. Menyatakan suatu algoritma
Setelah menetapkan model, lalu dibuat representasi atau menyatakan algoritma. Di sini harus dibuat barisan langkah-langkah atau instruksi secara teruut guna menyelesaikan suatu masalah. Pernyataan ini harus dibuat secara singkat, berhingga, terstruktur. Menyatakan algoritma dpt dgn dua cara yaitu: diagram atau pseudococe (bahasa semu)
3. Validasi Algoritma
Indikasi dari suatu algoritma yang valid adalah jika penyelesaiannya memenuhi solusi yang sebenarnya. Penyelesaian yg diperoleh harus memecahkan masalah bukan menimbulkan masalah baru. Perhitungan, prosedur, solusi harus selalu benar utk semua jenis kemungkinan masukan.
4. Menganalisis suatu Algoritma
Algoritma dapat dianalisis dari dua sisi yaitu masalah running time yang diperlukan serta besarnya storage/memori yang terlibat. Atau secara singkat yang dianalisis adalah:
Speed & Storage
dua hal ini selalu dikaitkan/dibandingkan dengan ukuran input yang diberikan.
5. Menguji Algoritma Algoritma diuji dengan cara membuat program komputernya. Ada dua fase pengujian:
- Fase debugging; ini utk menemukan kesalahan program baik sintak maupun logika
- Fase profiling; jika sdh benar, maka dapat diukur running time dan pengunaan storage/memorinya
ANALISIS ALGORITMA:
Waktu tempuh (running time)
Waktu tempuh (running time)
- Yang mempengaruhi waktu tempuh adalah:
- Banyaknya langkah
- Besar dan jenis input
- Jenis operasi
- Komputer dan kompilator
ANALISIS ALGORITMA:
Jumlah memori/storage
- Tergantung dari:
- Banyaknya langkah
- Jenis variabel/data yg digunakan
Kompleksitas waktu
Kompleksitas waktu adalah sebuah fungsi f(n) yang diberikan untuk menyatakan waktu tempuh dan kebutuhan storage dengan ukuran n input data.
Definisi 1.
F(n) merupakan “big oh” dari G(n) dengan notasi F(n) = O(G(n)) jika dan hanya jika tedapat dua konstanta bulat positif C dan no sedemikian hingga |F(n)| C |G(n)| untuk setiap n > no
Definisi 2
F(n) merupakan “omega” dari G(n) dengan notasi F(n) = Ω (G(n)) jika dan hanya jika terdapat dua buah konstanta positif C dan m sedemikian hingga |F(n)| C |G(n)| untuk setiap n m.
Definisi 3
F(n) merupakan “theta” dari G(n) dengan notasi F(n) = Ө (G(n)) jika dan hanya jika terdapat dua buah konstanta positif C1, C2 dan m sedemikian hingga
C1 |F(n)| C2 |G(n)| untuk setiap n m.
Teorema 1:
Jika F(n) adalah fungsi polinomial dalam n dengan derajat m, yang ditulis dengan:
F(n) = am Nm + am-1 Nm-1 + … + a1 N + a0
Maka ‘Big Oh’ dari F(n) adalah Nm yang dinotasikan:
F(n) = O(Nm)
Keadaan kompleksitas waktu
- Worst case (nilai maksimum dari nilai F(n) utk semua input yg mungkin. Keadaan yang terburuk dr suatu algoritma)
- Average case (keadaan dr waktu tempuh yg ekivalen dgn nilai ekspektasi dari F(n) utk setiap input data yang mungkin. Nilai ekspektasi didefinisikan sbg:
E= n1 p1 + n2 p2 + ….. + nk pk
n = nilai nilai yang muncul
p = probabilitas dr setiap n yg muncul
cont
3. Best case (suatu keadaan yang merupakan nilai minimum dari F(n) untuk setiap input yang mungkin. Ini keadaan yang terbaik dari suatu algoritma. Dgn demikian waktu tempuhnya minimal.
Contoh:
Jika suatu fungsi F(n)= 3n3 + 2n2 merupakan suatu fungsi dari waktu tempuh, maka big oh –nya adalah n3 yang dinotasikan sebagai:
F(n) = O(n3)
cont
Dari definisi diperoleh:
Jika F(n) = O(n3) mk akan terdapat dua bilangan C dan n0 yaitu:
F(0) = 0 -> n0 =0
F(1) = 5 -> C = 5
Sedemikian hingga berlaku pertidaksamaan:
3n3 + 2n2 ≤ 5 n3 utk setiap n 0
ORDER STATISTIC
Menentukan elemen terkecil ke-k dari n elemen data
Pendahuluan : Order Statistic
- Mencari unsur terkecil ke-k dari n unsur (http://en.wikipedia.org/wiki/Order_statistic)
Algoritma Sederhana
Begin
Algoritma Linear
Algoritma Linear
Function SELECT(k,n,S):integer;
Analisa Algoritma
- Operasi Dominan : Perbandingan
- Kompleksitas : O(n)
- Kompleksitas waktu
g(n) ≤ cn untuk n < 50
g(n) ≤ g(n/5) + g(3n/4) + cn untuk n ≥ 50
Analisa Algoritma (lanjutan)
- Kompleksitas Memori :
membutuhkan memori yang cukup besar karena terdapat dua pemanggilan rekursif dan parameternya bertipe array.
- Kemudahan :
Algoritma sederhana lebih efisien dibandingkanalgoritma linear, selain implementasinya sederhana,memori yang diperlukan juga tidak terlalu besar serta datanya menjadi terurut.
Kesimpulan
- Terdapat dua algoritma untuk mencari elemen terkecil ke-k, yaitu algoritma linear dan algoritma sederhana.
- Algoritma Linear menggunakan teknik devide and conquer dan teknik programming rekursif.
- Algoritma linear lebih cepat dibanding algoritma sederhana, akan tetapi perbedaan kecepatannya relatif kecil.
- Hanya mendapatkan nilai terkecil ke-k, untuk satu nilai k. Untuk nilai k yang lain harus dicari dari awal kembali
- Algoritma sederhana lebih efisien dibandingkan dengan algoritma linear, selain implementasinya sederhana, juga memori yang digunakan tidak terlalu besar dan selain itu algoritma sederhana mempunyai nilai tambah yaitu datanya menjadi terurut.
- Untuk menanggulangi kebutuhan memori yang besar pada algoritma linear, disarankan untuk menngunakan struktur data pointer.
