Rekayasa Perangkat Lunak

Design and Analysis of AlgorithmFundamentals of Algorithm Analysis in Efficiency

Aryo Pinandito, ST, M.MT - PTIIK UBAnalisis AlgoritmaAnalisis Algoritma bertujuan memeriksa efisiensi algoritma dari dua segi : waktu eksekusi dan penggunaan memori

Efisiensi waktu seberapa cepat algoritma dieksekusiEfisiensi memori berapa banyak memori yang dibutuhkan untuk menjalankan algoritma2Analisis Efisiensi Waktu AlgoritmaUntuk melakukan analisa efisiensi waktu algoritma harus diestimasi dulu waktu eksekusi algoritma3Algorithm sequential search (A[0..n-1], K) Searches for a given value in a given array by sequential searchInput: an array A[0..n-1] and a search key KOutput: returns the index of the first element of A that matches K or -1 if there are no matching elementsi 01xwhile i n and A[i] K do2x i i + 11xif i n return i 2xelse return -11x4Analisis Algoritma Sequential SearchBaris kode mana yang sangat berpengaruh pada running time?

Bagian loop (baris 2 dan 3). Mengapa?

Karena dieksekusi berulangulang.Makin banyak eksekusinya, makin lama running time program5Sequential Searchi 01xwhile i n and A[i] K do2x i i + 11xif i n return i 2xelse return -11x

Estimasi waktu eksekusi algoritma sequential search?

time = nLoop x tLooptime = estimasi waktu eksekusi algoritma untuk input tertentu

nLoop: berapa kali loop dieksekusitLoop: waktu yang diperlukan untuk mengeksekusi loop 1 kali. Biasanya ditentukan 1 satuan waktu tanpa dispesifikasikan berapa nilainya

7Case: Best, Average, WorstAsumsikan array A terdiri atas n elemen.

Best case: k ditemukan di elemen pertama array A. time = 1 x 1 satuan waktu Average case: k ditemukan di elemen tengah array A. time = n/2 x 1 satuan waktu Worst case: k ditemukan di elemen paling akhir array A. time = n x 1 satuan waktu8Analisis Algoritma Non-RekursifLangkah-langkah umum untuk menganalisa efisiensi waktu algoritma nonrekursif Tentukan parameter yang mengindikasikan ukuran inputIdentifikasi basic operation algoritmaTentukan apakah untuk ukuran input yang sama banyaknya eksekusi basic operation bisa berbedaTentukan rumus sigma yang menunjukkan berapa kali basic operation dieksekusiSelesaikan rumus sigma untuk menghitung banyaknya eksekusi basic operation91: Tentukan parameter yang mengindikasikan ukuran inputSesuatu pada input yang jika nilainya bertambah akan menyebabkan banyaknya eksekusi loop bertambahContoh, algoritma untuk menghitung Xn menggunakan cara Xn = X * X * X * * X sebanyak n kali. Parameter ukuran inputnya adalah nilai n, karena jika n makin besar, maka banyaknya eksekusi loop bertambahBagaimana dengan nilai X?

102: Identifikasi basic operation algoritmaWaktu yang diperlukan untuk mengeksekusi loop 1 kaliDapat diwakili oleh sebuah operasi pada loop paling dalam. Operasi yang dipilih adalah operasi yang selalu dilakukan ketika loop dieksekusiUntuk algoritma sequential search, basic operationnya dapat digunakan i ni n dieksekusi 1 kali setiap loop dieksekusi

113: Apakah untuk ukuran input yang sama, jumlah eksekusi basic operation dapat berbeda?Pada sequential search, parameter untuk ukuran input adalah n atau banyaknya elemen arrayUntuk n tertentu, apakah banyaknya eksekusi basic operation bisa berbeda?

Jika elemen pertama array input A bernilai K, maka banyaknya eksekusi basic operation untuk n tertentu C(n)= 1Jika K ditemukan di elemen terakhir, maka C(n)= nPerlu diadakan analisa best case, worst case dan average case

124A: Tentukan rumus sigma yang menunjukkan berapa kali basic operation dieksekusiC(n) = banyaknya eksekusi basic operation untuk input ukuran n

Best case Sequential Search:

Best case terjadi jika elemen pertama A bernilai K

4B: Tentukan rumus sigma yang menunjukkan berapa kali basic operation dieksekusiC(n) = banyaknya eksekusi basic operation untuk input ukuran n

Worst case Sequential Search:

Worst case terjadi jika elemen A yang bernilai bernilai K merupakan elemen terakhir atau tidak ada elemen A yang bernilai K

4C: Tentukan rumus sigma yang menunjukkan berapa kali basic operation dieksekusiAverage case pada sequential search

AsumsikanData K memang ada di AProbabilitas K terletak di elemen tertentu A dan terdistribusi secara merata.Probabilitas K terletak di elemen ke i = 1/n

Bentuk umum: i * 1 / n

4C: Tentukan rumus sigma yang menunjukkan berapa kali basic operation dieksekusiPosisi K ditemukanBanyaknya eksekusi basic operationProbabilitas terjadiKontribusi pada C(n)12n12n1/n1/nn1 * 1/n2 * 1/nN * 1/nAverage case pada sequential search:4C: Tentukan rumus sigma yang menunjukkan berapa kali basic operation dieksekusi

5: Selesaikan rumus sigma yang menunjukkan berapa kali basic operation dieksekusiBest case untuk sequential search

Untuk input berukuran n, basic operation dilakukan 1 kali

5: Selesaikan rumus sigma yang menunjukkan berapa kali basic operation dieksekusiWorst case untuk sequential search

Untuk input berukuran n, basic operation dilakukan n kali

5: Selesaikan rumus sigma yang menunjukkan berapa kali basic operation dieksekusiAverage case pada sequential search

To find the sum of a certain number of terms of an arithmetic sequence:

where Sn is the sum of n terms (nth partial sum), a1 is the first term, an is the nth term.5: Selesaikan rumus sigma yang menunjukkan berapa kali basic operation dieksekusiPada sequential search, average case-nya:

Untuk n = 10, C(n) = 5,5Apakah itu berarti K berada pada elemen 5 atau 6Apa artinya?

Estimasi Running Time Algoritma Sequential SearchT(n) = Cop* C(n)

Dimana:

T(n) = Waktu yang diperlukan untuk mengeksekusi algoritma dengan input berukuran nCop = Waktu untuk mengeksekusi basic operation 1 kali. Biasanya ditentukan sebagai 1 satuan waktu

Hitung T(n) untuk sequential search pada best case, worst case dan average case!22What is T(n) For?Apakah untuk mengestimasi running time algoritma?Tujuan utama mencari T(n) bukan mencari waktu eksak yang dibutuhkan untuk mengeksekusi sebuah algoritmaTetapi untuk mengetahui tingkat pertumbuhan waktu eksekusi algoritma jika ukuran input bertambah (order of growth / OoG) ExerciseSebuah algoritma memiliki T(n) = n 1. Estimasi waktu eksekusi algoritma jika jumlah masukannya memiliki anggota: 10 elemen 20 elemen 30 elemenBuat grafik yang menunjukkan hubungan antara banyaknya elemen yang dieksekusi dengan waktu eksekusi

Orders of Growth (OoG)Tingkat pertumbuhan waktu eksekusi algoritma jika ukuran input bertambahOrders of Growth are also known as Efficiency ClassesExerciseUrutkan waktu eksekusi algoritma T(14)(n) berdasar order of growthnya dari kecil ke besar

T1(n) = n2T1 (10) = 100 T1 (100) = 10,000T2(n) = n3T2(10) = 1,000T2(100) = 1,000,000T3(n) = nT3(10) = 10T3(100) = 100T4(n) = log2n T4(10) = 3.3T4(100) = 6.6

Membandingkan Orders of Growth dari dua AlgoritmaAlgoritma A dan B merupakan algoritma untuk menyelesaikan permasalahan yang sama. Untuk input berukuran n, waktu eksekusi algoritma A adalah TA(n) sedangkan waktu eksekusi algoritma B adalah TB(n). Orders of growth mana yang paling besar?

Membandingkan Orders of Growth dari dua Algoritma0 maka OoG TA(n) < OoG TB(n) C maka OoG TA(n) = OoG TB(n)~ maka OoG TA(n) > OoG TB(n)

Asymptotic NotationsO (big oh) (big omega) (big theta)29In the following discussionCS3024-FAZ30t(n) & g(n): any nonnegative functions defined on the set of natural numbers

t(n) an algorithm's running timeUsually indicated by its basic operation count C(n)g(n) some simple function to compare the count withO(g(n)): InformallyCS3024-FAZ31O(g(n)) is a set of all functions with a smaller or same order of growth as g(n)Examples:n O(n2); 100n + 5 O(n2) n(n-1) O(n2)n3 O(n2); 0.0001 n3 O(n2); n4+n+1 O(n2)(g(n)): InformallyCS3024-FAZ32(g(n)) is a set of all functions with a larger or same order of growth as g(n)Examples:n3 (n2) n(n-1) (n2)100n + 5 (n2)(g(n)): InformallyCS3024-FAZ33(g(n)) is a set of all functions with a same order of growth as g(n)Examples:an2+bn+c; a>0 (n2); n2+sin n (n2) n(n-1) (n2); n2+log n (n2)100n + 5 (n2); n3 (n2)=ExerciseTerdapat dua algoritma yang menyelesaikan permasalahan yang sama. Untuk input berukuran n, Algoritma 1: T1(n) = 30n2 + 2n + 5. Algoritma 2: T2(n) = n3 + n

Mana yang lebih besar, OoG T1 atau T2?Untuk n kecil mana yang anda pilih?Untuk n besar, mana yang anda pilih?Basic Efficiency ClassesThe time efficiency of a large number of algorithms fall into only few classes1 or C, log n, n, n log n, n2, n3, 2n, n!Multiplicative constants are ignored it is possible that an algorithm in worse efficiency class running faster than algorithm in better classExp: Alg A: n3, alg B: 106n2; unless n > 106, alg B runs faster than alg AKelas-kelas Orders of GrowthCconstantlog NlogarithmicNlinearN log Nlinear logaritmicN2quadraticN3cubic2NexponentialN!factorial

Makin ke bawah, OoG-nya makin besarGrafik Kelas-kelas OoG

Sifat OoGJika T(n) = T1(n) + T2(n) + + Ti(n)Maka OoG T(n) = max OoG(T1(n), T2(n), , Ti(n))

Jika T(n) = cf(n) Maka OoG T(n) = f(n)ExerciseTentukan kelas orders of growth dari:

T1(n) = 2n3 + 4n + 1T2(n) = 0,5 n! + n10T3(n) = n3 + n log nT4(n) = 2n + 4n3 + log n + 10

Order of Growth: Summary40(1) Waktu pelaksanaan algoritma adalah tetap, tidak bergantung pada ukuran input. (log n) Kompleksitas waktu logaritmik berarti laju pertumbuhan waktunya berjalan lebih lambat daripada pertumbuhan n.(n) Bila n dijadikan dua kali semula, maka waktu pelaksanaan algoritma juga dua kali semula.(n log n) Bila n dijadikan dua kali semula, maka n log n menjadi lebih dari dua kali semula (tetapi tidak terlalu banyak)

40Order of Growth: Summary41(n2)Bila n dinaikkan menjadi dua kali semula, maka waktu pelaksanaan algoritma meningkat menjadi empat kali semula.(n3)Bila n dinaikkan menjadi dua kali semula, waktu pelaksanan algoritma meningkat menjadi delapan kali semula.(2n)Bila n dijadikan dua kali semula, waktu pelaksanaan menjadi kuadrat kali semula!(n!)Bila n dijadikan dua kali semula, maka waktu pelaksanaan algoritma menjadi faktorial dari 2n.

41Terima KasihThank YouDankeGratiasMerciKiitosGrazias