Algoritma dan Struktur Data Click to edit Master subtitle style
Pertemuan 3 Pengantar Analisis Efisiensi Algoritma
Analisa efisiensi algoritma bertujuan mengestimasi waktu dan memori yang dibutuhkan untuk mengeksekusi sebuah algoritma atau fungsi Ø
Ø
Efisiensi waktu seberapa cepat algoritma dieksekusi Efisiensi memori berapa banyak memori yang dibutuhkan untuk menjalankan algoritma
Faktor apa yang mempengaruhi efisiensi waktu sebuah algoritma?
Ukuran input banyaknya data input yang diolah oleh algoritma Contoh : ??? Basic operation bagian dari algoritma yang yang dieksekusi berulang - ulang
Algorithm
sequential search (A[0..n-1], K)
// searches for a given value in a given array by sequential search // input: an array A[0..n-1] and a search key K // output: returns the index of the first element of A that matches K or -1 if there are no matching elements
i0
1x
while i n and A[i] K do ii+1
1x
if i n return i
2x
else return -1
2x
1x
Jelaskan isi algoritma di atas
Berapa ukuran input algoritma sequential search? Tunjukkan basic operationnya
Ø
Ø
Basic operation selalu merupakan bagian loop paling dalam. Mengapa??? Bagian program non basic operation memberi tambahan sangat kecil pada waktu eksekusi program
Sequential Search i0
1x
while i n and A[i] K do ii+1 if i n return i else return -1
2x
1x 2x 1x
Estimasikan waktu eksekusi algoritma sequential search!
T(n) = cop x C(n)
T(n) = estimasi waktu eksekusi algoritma untuk input berukuran n Cop = waktu untuk mengeksekusi basic operation satu kali. Biasanya ditentukan 1 satuan waktu. Pada contoh sequential search, 1 satuan waktu kira - kira membutuhkan berapa clock CPU???
T(n) = cop x C(n)
C(n) berapa kali basic operation dieksekusi untuk data berukuran n Pada kasus sequential search nilai C(n) tergantung dari posisi elemen yang akan dicari
Best Case, Worst Case, Average Case Best-case Anda beruntung. Nilai yang dicari ada pada posisi awal array. Setelah nilainya ditemukan, algoritma selesai dieksekusi. C(n) = 1 dan T(n) = 1 satuan waktu
Worst-case Anda sial. Nilai yang dicari ada di posisi terakhir array atau tidak ada di array. C(n) = n dan T(n) = n satuan waktu
Average-case Kasus paling umum. Nilai yang dicari bisa terletak di elemen
Average Case Asumsikan 1. 2.
Data yang dicari memang ada pada array Probabilitas data yang dicari terdapat di elemen tertentu sama besar untuk semua elemen array. Sehingga probabilitas sebuah data muncul pada elemen ke i adalah 1/n
Average Case Banyaknya eksekusi basic operation jika data yang dicari ada pada posisi 1st position = 1 2nd position = 2 ……. ith position = i ……. nth position = n
Average Case C(n) atau banyaknya eksekusi basic operation untuk data berukuran n 1(1/n) + 2 (1/n) + 3 (1/n) + …….. + i (1/ n) + …… + n (p/n) = (1/n)(1 + 2 + 3 +… + n) = (1/n)(n(n+1))/2 = (n+1)/2
T(n) = (n+1)/2 satuan waktu
Catatan Ø
Ø
Tujuan utama mencari T(n) bukan mencari waktu eksak yang dibutuhkan untuk mengeksekusi sebuah algoritma Tetapi untuk mengetahui tingkat pertambahan waktu eksekusi algoritma jika ukuran input bertambah (order of growth)
Orders of Growth Tingkat pertambahan waktu eksekusi algoritma jika ukuran input bertambah
Orders of Growth Urutkan waktu eksekusi algoritma di bawah ini berdasarkan order of growthnya T1 (n) = n2
T1 (10) = 100
T1 (100) = 10,000
T2(n) = 2n
T2(10) = 1,028
T2(100) = 1.3 x 030
T3(n) = n3
T3(10) = 1,000
T3(100) = 1,000,000
T4(n) = n
T4(10) = 10
T5(n) = log2 n
T5(10) = 3.3
T4(100) = 100 T5(100) = 6.6
Orders of Growth C logN N NlogN N2 N3 2N N!
Ø Ø
constant, we write O(1) logarithmic linear quadratic cubic exponential factorial
Makin ke bawah, order of growth makin besar Untuk input data berukuran besar, algoritma dengan order of growth besar eksekusi waktunya jauh lebih lama dari algoritma dengan order of growth kecil
The Big-Oh Notation f(n) Є O(g(n)) Cara membaca “f(n) berada pada kelas g(n)” f(n) Є O(g(n)) Jika orders of growth f(n) kurang atau sama dengan(n).
The Big-Oh Notation C logN N NlogN N2 N3 2N N!
constant, we write O(1) logarithmic linear quadratic cubic exponential factorial N2 Є O(N2) paling presisi NlogN Є O(N2) N Є O(N2) log2N Є O(N2) logN Є O(N2) C Є O(N2)
O(1) Waktu pelaksanaan algoritma adalah tetap, tidak bergantung pada ukuran masukan.
O(log n) Kompleksitas waktu logaritmik berarti laju pertumbuhan waktunya berjalan lebih lambat daripada pertumbuhan n.
Rinaldi M/IF2091 Strukdis
1919
O(n) Bila n dijadikan dua kali semula, maka waktu pelaksanaan algoritma juga dua kali semula. O(n log n) Bila n dijadikan dua kali semual, maka n log n menjadi lebih dari dua kali semula (tetapi tidak terlalu banyak)
Rinaldi M/IF2091 Strukdis
2020
O(n2) Bila n dinaikkan menjadi dua kali semula, maka waktu pelaksanaan algoritma meningkat menjadi empat kali semula.
O(n3) Bila n dinaikkan menjadi dua kali semula, waktu pelaksanan algoritma meningkat menjadi delapan kali semula.
Rinaldi M/IF2091 Strukdis
2121
O(2n) Bila n dijadikan dua kali semula, waktu pelaksanaan menjadi kuadrat kali semula!
O(n!) Bila n dijadikan dua kali semula, maka waktu pelaksanaan algoritma menjadi faktorial dari 2n.
Rinaldi M/IF2091 Strukdis
2222
Nilai masing-masing fungsi untuk setiap bermacam-macam nilai n log n 0 1 2 3 4 5
n 1 2 4 9 16 32
n log n 0 2 8 24 64 160
n2
n3
2n
1 4 16 64 256 1024
1 8 64 512 4096 32768
2 4 16 256 65536 4294967296
Rinaldi M/IF2091 Strukdis
n! 1 2 24 362880 20922789888000 (terlalu besar )
2323
Tugas Implementasikan bubble sort dalam bahasa C vHitung T(n) untuk bubble sort vEfisiensi waktu bubble sort berada pada kelas apa? v
v
v
Dikumpulkan dan dibahas pada pertemuan pertama setelah libur lebaran Tugas dipresentasikan oleh mahasiswa yang memiliki nomor urut mod 10 == 8
