Analisa Kompleksitas Algoritma. Sunu Wibirama

Analisa Kompleksitas Algoritma Sunu Wibirama

Referensi ✦

✦

✦

✦

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., Introduction to Algorithms 2nd Edition, Massachusetts: MIT Press, 2002 Sedgewick, R., Algorithms in C++ Part 1-4, Massachusetts: Addison-Wesley Publisher, 1998 Video lecture MIT Opencourseware ke-1: Introduction Video lecture IIT Kharagpur, India ke-18: Complexity of Algorithm

Video lecture MIT Opencourseware ke-1: Introduction

Video lecture IIT Kharagpur, India ke-18: Complexity of Algorithm

Agenda Hari Ini • Pentingnya Analisa Algoritma • Prinsip Perbandingan Algoritma • Dasar-dasar Matematika dan Teori Big-O • Contoh Implementasi • Kesimpulan

Apa yang pertama kali Anda menjadi pertimbangan Anda saat membeli komputer, selain PERFORMA?

• • • • • • • •

Kehandalan dalam menyelesaikan masalah (robustness) Fungsionalitas (functionality) Tampilan grafis (user interface) Daya tahan (reliability) Keamanan (security) Kesederhanaan (simplicity) Kemudahan dalam penggunaan (user friendly) Kemudahan dalam pemeliharaan (maintainability)

Algoritma dan Performa •

Hal-hal yang menjadi pertimbangan utama Anda tidak muncul dengan gratis

• • •

Performa sistem menjadi alat tukar seperti uang. Algoritma program memegang peran kunci Algoritma adalah teknologi, engineered, sebagaimana perangkat keras komputer

Pentingnya Analisa Algoritma •

Algoritma membantu kita memahami skalabilitas program kita

•

Performa terkadang menjadi pembeda antara yang mungkin dilakukan dan yang tidak mungkin dilakukan

•

Analisa algoritma memberi gambaran informasi tentang ‘perilaku program’ kita

•

Mempelajari bagaimana menerapkan algoritma yang baik untuk kasus tertentu membedakan profesi system analyst dan programmer

Prinsip Perbandingan Algoritma •

•

•

Apa yang membuat sebuah algoritma dikatakan LEBIH BAIK dari algoritma yang lain?

• •

Kompleksitas waktu (Time Complexity) Kompleksitas ruang (Space Complexity)

Kecenderungan saat ini:

• • •

ruang (hard disk) semakin murah kapasitas data yang diproses semakin besar waktu pemrosesan harus semakin cepat

Kompleksitas waktu menjadi variabel yang sangat penting

Penyebab variasi pada hasil analisa algoritma

•

Program aras tinggi diterjemahkan ke bahasa mesin. Setiap tipe prosesor memiliki prosedur bahasa mesin yang berbeda

•

Aplikasi dijalankan di shared environment, sehingga terpengaruh oleh penggunaan memori

•

Program sangat sensitif terhadap masukan dan akan menunjukkan performa yang jauh berbeda untuk rentang masukan yang tidak terlalu berbeda

•

Program tidak dipahami dengan baik, sehingga analisa matematika kurang merepresentasikan kondisi yang sesungguhnya

•

Program tersebut memang tidak bisa dibandingkan dengan program yang lain karena hanya optimal untuk input-input tertentu

Hal-hal yang perlu diperhatikan pada analisa algoritma

• Memisahkan operasi pada tingkat abstraksi

dan implementasi. Contoh: menghitung jumlah instruksi scanf pada program lebih diprioritaskan daripada memahami berapa nanoseconds instruksi scanf dieksekusi

• Mengidentifikasi data masukan:

- Strategi average dan worst case - Strategi random dan biggest data

Dasar Matematika & Teori Big-O

•

Sebagian besar algoritma memiliki parameter primer N yang sangat mempengaruhi waktu eksekusi

•

Parameter N bisa berupa: - derajat polinomial - ukuran berkas (file) yang diproses - jumlah karakter pada text string - ukuran data yang diproses

•

Pengukuran kompleksitas: Big-O

3.1 Asymptotic notation

c2 g(n)

cg(n)

Teori Big-O

f (n)

f (n)

c1 g(n)

n0

n

n0

f (n) = !(g(n))

Teorema Matematika: (a)

n f (n) = O(g(n)) (b)

n0

f (n) = " (c)

O(g(N )) = { f (N ) : jika terdapat konstanta positif c dan N 0 , sehingga Figure 3.1 Graphic examples of the !, O, and " notations. In each part, the value of the minimum possible value; any greater value would also work. (a) !-notation bounds a 0 ≤ f (Nwithin ) ≤ constant cg(Nfactors. ) untuk N ≥if there N 0 }exist positive constants n0, c1, We writesemua f (n) = !(g(n))

that to the right of n 0 , the value of f (n) always lies between c1 g(n) and c2 g(n) inclus notation gives an upper bound for a function to within a constant factor. We write f (n) if there are positive constants n 0 and c such that to the right of n 0 , the value of f (n) alw or below cg(n). (c) "-notation gives a lower bound for a function to within a constan write f (n) = "(g(n)) if there are positive constants n 0 and c such that to the right of n of f (n) always lies on or above cg(n).

Engineering: Hilangkan orde yang lebih rendah dan konstanta. Gunakan1 hanya orde tertinggi pada polinomialc n ≤ 2 n − 3n ≤ c n for 2all n ≥ n . Dividing by n yields3 3 Contoh: 3n + 90n −1 5n3 + 6046 = O(N )

•

1

2

2

2

0

c1 ≤

2

−

n

≤ c2 .

2

2

Macam-macam Parameter N 1

log N

Sebagian besar instruksi dieksekusi satu kali atau dalam jumlah yang tidak terlalu banyak (waktu eksekusi konstan) Pertumbuhan waktu eksekusi program tidak terlalu cepat. Waktu eksekusi ini terdapat pada program yang memecahkan masalah dengan kapasitas yang cukup besar, dipecah-pecah menjadi beberapa bagian

N

Waktu eksekusi program linier. Sebagian besar masukan diproses dalam jumlah yang tidak terlalu banyak

N log N

Waktu eksekusi ini terdapat pada program yang memecahkan masalah menjadi beberapa bagian, menyelesaikannya secara terpisah, kemudian menggabungkannya kembali

Macam-macam Parameter N (cont’d) 2

Biasanya digunakan untuk memecahkan masalah dalam jumlah kecil. Biasanya terdapat pada program yang memproses pasangan data (quadratic) atau array dua dimensi secara bersamaan (double-nested loop)

N

3

Biasanya digunakan untuk memecahkan masalah dalam jumlah kecil. Biasanya terdapat pada program yang memproses tiga buah data (cubic) atau array tiga dimensi secara bersamaan (triple-nested loop)

2

N

Waktu eksekusi program linier. Sebagian besar masukan diproses dalam jumlah yang tidak terlalu banyak

N

Beberapa perbandingan kompleksitas algoritma

Getting Started

Figure 1-1 shows how the various measures of complexity compare with one another. The horizontal axis represents the size of the problem — for example, the number of records to process in a search algorithm. The vertical axis represents the computational effort required by algorithms of each class. This is not indicative of the running time or the CPU cycles consumed; it merely gives an indication of how the computational resources will increase as the size of the problem to be solved increases.

O(N2)

Running Time (seconds)

O(N log N)

O(N!)

O(N)

O(1)

O(log N) Figure 1-1: Comparison of different orders of complexity.

Input size (N)

Referring back at the list, you may have noticed that none of the orders contain constants. That is, if an

Formula Kondisi Periodik • Sebagian besar algoritma terdiri dari proses

penyelesaian masalah dengan memanfaatkan perulangan (rekursif)

• Bagian yang berulang tersebut secara tidak langsung berkontribusi pada kompleksitas sebuah algoritma

• Perlu mengetahui formula-formula dasar untuk kondisi periodik

Formula Kondisi Periodik •

Formula 1: kondisi periodik muncul pada program rekursif yang mengeliminasi satu item input

Sedgewick, R., Algorithms in C++ Part 1-4, Massachusetts: Addison-Wesley Publisher, 1998


Formula 2: kondisi periodik muncul pada program rekursif yang membagi input menjadi dua bagian hanya dengan satu langkah



Formula 3: kondisi periodik muncul pada program rekursif yang membagi input menjadi dua bagian, namun perlu memeriksa tiap-tiap input



Formula 4: kondisi periodik muncul pada program rekursif yang mengolah input secara linear sebelum, pada saat, dan sesudah membagi input menjadi dua bagian



Formula 5: kondisi periodik muncul pada program rekursif yang membagi input menjadi dua bagian, kemudian mengerjakan input lain dengan kapasitas konstan


Jenis analisa waktu eksekusi

• Strategi Worst case (umum digunakan)

T(N) = waktu eksekusi maksimum untuk jumlah data N

• Strategi Average case (jarang digunakan)

T(N) = waktu yang diharapkan dari sebuah algoritma untuk mengeksekusi data sejumlah N. Perlu ada asumsi statistik untuk distribusi data masukan

Analisa worst case •

Biasanya mengambil batas maksimal (upper bound), untuk memberi jaminan bahwa program tidak akan terus berjalan saat batas maksimal waktu eksekusi tercapai

•

Waktu eksekusi juga tergantung pada kondisi awal input : data yang sudah terproses akan lebih mudah dieksekusi daripada yang belum

•

Untuk worst-case, diambil kemungkinan yang paling buruk (data tidak terproses sama sekali, pada kondisi yang berlawanan dengan kondisi akhir yang diharapkan)

Machine-independent Running Time •

Berapakah waktu eksekusi terburuk (worst-case) dari sebuah algoritma?

•

Tergantung dari kecepatan mesin kita: - kecepatan relatif: berjalan di komputer yang sama - kecepatan absolut: berjalan di komputer yang berbeda

•

Kita ingin mengukur kecepatan algoritma tanpa mempertimbangkan kecepatan komputer

Analisa Asymptotic : Pertumbuhan waktu eksekusi T(N) saat N → ∞

!"#$%&'&()*%+,-',$./)+ Performa Asymptotic Pada jumlah data tertentu (> N 0), algoritma+ dengan kompleksitas 57"<(" ?"$6(:@'?"("<89?7*(@(Θ2" 3 @:?8'>$7%( rendah O(n2) bisa saja lebih efisien dibandingkan algoritma 13 @:?8'>$7%0 ?,B?30 &"@$6(@(Θ2" dengan kompleksitas tinggi

A2"3

O(n2) O(n3)

" !"#$"%&"'()*(+,,-

",

4 5"(6789:;<=$(>?<8'"( Kita tidak boleh meremehkan sebuah algoritma yang secara @6A%#$8$>B@::A(6:8C"'( asymptotic lebih lambat @:?8'>$7%6*(78C"D"'0 4 E"@:FC8':;(;"6>?<( Dalam disain riil, kita perlu 6>$9@$>8<6(8G$"<(B@::(G8'(@( menyeimbangkan proses engineering B@'"G9:(&@:@<""'>D"60 4 I6A%#$8$>B(@<@:A6>6(>6(@( Analisa Asymptotic membantu 96"G9:($88:($8(7":#($8( kita untuk berlaku lebih adil 6$'9B$9'"(89'($7><J>
1%23$)-.#*4 566789*:$);*<=*<>/?)"> ?"&*1.?$,>0*:=*@>)0>$0%"

gunakan !"#$%&'(#)%"*#%*+,-%$)#./0

./0+1

Teori Big-O • Untuk membandingkan dua buah algoritma, bandingkan tingkat kompleksitasnya

f (N ) lim →∞ N →∞ g(N )

Untuk N besar g(N) lebih efisien dari f(N)

f (N ) lim →0 N →∞ g(N )

Untuk N besar f(N) lebih efisien dari g(N)

!"#$%&'()#*$'+$,'&-./0

Implementasi: Insertion Sort !"#$%& 1"23"45"((¢?/*(?+*(6*(?"² 78(43%&"'10 '$%#$%& #"'%3$9$:74((¢?A/B*?A+B*6B*?A"² 135; $;9$((?A/ ≤ ?A+ ≤ 6 ≤ ?A" 0 123*%)#4 !"#$%& <((+((=((>((?((@ '$%#$%& +((?((=((@((<((> !"#$"%&"'()*(+,,-

1%23$)-.#*4 566789*:$);*<=*<>/?)"> ?"&*1.?$,>0*:=*@>)0>$0%"

!"#$%&'(#)%"*#%*+,-%$)#./0

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., Introduction to Algorithms 2nd Edition, Massachusetts: MIT Press, 2002

./0-

2 + 1 3 4 5 !"#$%&'()*(+,-'./+),(-)./ !"#$%&'()*(+,-'./+),(-)./

+1 2+ 12 33 Sort 44 55 Implementasi:!"#$%&'()*(+,-'./+),(-)./ Insertion 2 + 3 4 5 1

!"#$%&'()*(+,-'./+),(-)./!"#$%&'()*(+,-'./+),(-)./ + 1 2 3 4 5 1 + 2 3 4 5 !"#$%&'()*(+,-'./+),(-)./ !"#$%&'()*(+,-'./+),(-)./ 2 + 3 1 4 5 1 + 2 3 4 5 !"#$%&'()*(+,-'./+),(-)./

!"#$%&'()*(+,-'./+),(-)./

+ +1 ++1 ++ + + ++ ++

11+ ++1 222 333 444 555 !"#$%&'()*(+,-'./+),(-)./ !"#$"%&"'()*(+,,++ 11 22 33 44 55 + 2 + 3 4 1 5 !"#$"%&"'()*(+,,+ + 2 1 3 4 !"#$"%&"'()*(+,,5 + 2 3 4 1 5

%&"'()*(+,,-

%&"'()*(+,,%&"'()*(+,,-

%&"'()*(+,,%&"'()*(+,,-

+

3

2

4

1

1%23$)-.#*4 566789*:$);*<=*<>/?)"> ?"&*1.?$,>0*:=*@>)0>$0%"

!"#$%&'(#)%"*#%*+,-%$)#./0

!"#$%&'(#)%"*#%*+,-%$)#./0 !"#$%&'(#)%"*#%*+,-%$)#./0

2 32 2 1 22 2 1 21 31

3 43 3 3 43 3 3 43 23

4

2

1

!"#$%&'(#)%"*#%*+,-%$)#./0

3

1%23$)-.#*4 566789*:$);*<=*<>/?)"> ?"&*1.?$,>0*:=*@>)0>$0%"

!"#$%&'(#)%"*#%*+,-%$)#./0 1%23$)-.#*4 566789*:$);*<=*<>/?)"> ?"&*1.?$,>0*:=*@>)0>$0%"

4

2

5

!"#$%&'(#)%"*#%*+,-%$)#./0

1

1%23$)-.#*4 566789*:$);*<=*<>/?)"> 566789*:$);*<=*<>/?)"> ?"&*1.?$,>0*:=*@>)0>$0%" ?"&*1.?$,>0*:=*@>)0>$0%" 1%23$)-.#*4

!"#$%&'(#)%"*#%*+,-%$)#./0 !"#$%&'(#)%"*#%*+,-%$)#./0

./01 ./0/,

./0// ./0/+

5 15 5 5 15 5 5 15 15

!"#$%&'(#)%"*#%*+,-%$)#./0


1%23$)-.#*4 566789*:$);*<=*<>/?)"> ?"&*1.?$,>0*:=*@>)0>$0%" !"#$%&'(#)%"*#%*+,-%$)#./0 1%23$)-.#*4 566789*:$);*<=*<>/?)"> ?"&*1.?$,>0*:=*@>)0>$0%"

4 54 4 4 54 4 4 54 44

1%23$)-.#*4 566789*:$);*<=*<>/?)"> ?"&*1.?$,>0*:=*@>)0>$0%"

!"#$"%&"'()*(+,,- ./01 !"#$"%&"'()*(+,,-

1%23$)-.#*4 566789*:$);*<=*<>/?)"> ?"&*1.?$,>0*:=*@>)0>$0%"

1%23$)-.#*4 566789*:$);*<=*<>/?)"> ?"&*1.?$,>0*:=*@>)0>$0%"

5

1 2+ 12+ 31 1 2 32 52

./0/1

5 ./0/./0/1

3 &%">

./0/) ./0/1

Implementasi: !"#$%&'(")#(%&Insertion Sort 12!3451627!645(8+*("9 ຆ +:/(0(0("; *(% A*ĸ + &( " +( ;>3*ĸ +:(A; )*ĸ A*B / ,-'.$ )*C*, <=>(+:);(?(;>3 +( +:)D/;(ĸ +:); )*ĸ )*B / +:)D/;(@(;>3

A#B"C>DED>"F

/

)

A

"

+G BD'$"> !"#$"%&"'()*(+,,-

;>3

1%23$)-.#*4 566789*:$);*<=*<>/?)"> ?"&*1.?$,>0*:=*@>)0>$0%"

!"#$%&'(#)%"*#%*+,-%$)#./0


./0)

2 do key ← A[ j ] c2 n−1 case occurs if the array is already sorted. For each j = 2, 3, . . . , n, we then find andInsert so they nothe time. 3 ! A[ take j ] into sorted that A[i] ≤ key in line 5 when i has its initial value of j − 1. Thus t j = 1 2.2 for Analyzing algorithms sequence A[1 . . j − 1]. 0 n−1 j = 2, 3, . .I.NSERTION , n, and the-Sbest-case ORT (A) running time is cost times 4 i ← j −1 c4 n!− 1 21)to+A[i] length[A] cn 1 t n case occurs if the array is already sorte 5T (n) = 1while 0−and + ic2j> (n← c4 (n>−key 1) + c5 (n − 1)c+ c (n − 1) c1 n for 5 8 j j =2 !cn 2 2 do key ← A[ j ] n − 1 that A[i] ≤ key in line 5 when i has i 6 doc2A[i 1] ← A[i] c (t − 1) = (c1 + + c+ + c + c )n − (c + c + c + c ) . 4 5 4 56 8 j = 2, 3, . . . , n, and the best-case runni !nj =2 j 3 ! Insert A[8 j ] into 2the sorted 7This running time can i← i − 1 sequence c7 (t j −depend . j constants − 1]. n1) − 1 Ton be expressed as an A[1 + b .for a and0j =2 b that (n) = c1 n + c2 (n − 1) + c4 (n − 1 8the statement A[i + 1] ← key c n − 1 8 4 costs ci ; iti is←thus j −a 1linear function of n. c4 n!− 1 = (c1 + c2 + c4 + c5 + c8 )n − n 5 is in reverse whilesorted i > 0order—that and A[i] >is,keyin decreasing corder—the tj If the array worst 5 j =2 ! Theresults. running time of the algorithm is the sum for each n entire This running time can be expressed as a case each+element A[of j ] running with eachtimes element in thestatement 6 We must compare do A[i 1] ← A[i] c6 (t j − 1) j =2 the statement costs ci ; it is thus a linear ! tofor execute and is. , executed nthat times will executed; a statement that takes cso i steps n = j j = 2, 3, . . n. Noting sorted subarray A[1 . . j − 1], and t j i ← i − 15 c7 (t j If−the contribute c7i n to the total running time. To compute T (n), the runningj =2 time of1) array is in reverse sorted orde n 8+ A[i + 1]products ← key of the cost and times columns, c8 n obtaining − 1 case results. We must compare each ele n(n-S 1) , we sum I! NSERTION ORT the j= −1 sorted subarray A[1 . . j − 1], and so t j 2 nis the sum" n running times for each statement j =2 The running time of the algorithm" of n ! n(n + 1) T (n) = cexecuted; 1) + c (n − 1) + c t + c (t − 1) 1 n + c2 (na− 4 5 j 6 j j = statement that takes ci steps to execute and is executed n times will − 1 and 2 j =2 5 j =2 j =2 contribute c n to the total running time. To compute T (n), the running time of i n ! n(n − 1) n " NSERTION -S ORT, we sum the products of the cost and times columns, and obtaining ( j − 1) I= + c7 2 (t j − 1) + c8 (n − 1) . n j =2 ! n n n(n − 1) " " j =2 ( j − 1) = T (n)A for = a creview − 1)to+solve c4 (nthese − 1) summations), + c5 t j + cwe (t jthat − 1) 2 1 n + cof 2 (nhow 6 find (see Appendix j in =2 Even inputs of a given an algorithm’s j =2 depend on the worstforcase, the running timesize, of I NSERTION -S ORT running is j =2 time may Appendix A for a review of how t n -S ORT, the(see best which input of that size is given. For example, in I NSERTION " " # the worst case, the running time of I NSE + .1) + c7 (t j − 1) + c8 (nn(n − 1) T (n) = c1 n + c2 (n − 1) + c4 (n − 1) + c5 −1 j =2 2 T (n) = c1 n + c2 (n − 1) + c4 (n − 1 " # " # 5 This characteristic does not necessarily hold for a resource such as memory. A statement that n(n −inputs 1) of a given n(n −size, 1) an algorithm’s running time may Even for depend on" # " +executed c7 + cnot − 1) + c6of memory and is 8 (nnecessarily references m words n times does consume mn words of n(n − 1) n( 2 of that size is given. 2 NSERTION -S ORT , the best which input For example, in I + c + c 6 7 memory in total. $c $ % % 2 c c c c c 5 6 7 5 6 7 $c = + + − − + c8 n n 2 + c1 + c2 + c4 + c6 c7 % 2 $ 5 2 2 2 2 2 2 = + + n + c1 + 2 2 2 5− (c2characteristic + c4 + c5 + c8 )not . necessarily hold for a resource such as memory. A statement that This does

O(n )

−2(c2 + c4 + c5 + c8 ) .

references m words of memory and is executed n2 times does not necessarily consume mn words of This worst-case running b, worst-case running time can be exp memory in total.time can be expressed as an + bn + c for constants a,This

Implementasi: Insertion Sort Worst-case (seluruh input diurutkan terbalik): N

T (N ) = ∑ O( j) = O(n ) 2

Deret aritmatika

j=2

Apakah Insertion Sort algoritma yang cepat? - Ya, jika N kecil - Tidak, jika N besar Lihat perbandingannya dengan Merge Sort di slide berikutnya Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., Introduction to Algorithms 2nd Edition, Massachusetts: MIT Press, 2002

Contoh komparasi •

Komputer A: Insertion Sort, lebih cepat untuk N kecil, 2 memproses N data dengan waktu eksekusi c1 N Kecepatan eksekusi prosesor 109 instruksi/detik

•

Komputer B: Merge Sort, lebih lambat untuk N kecil, memproses N data dengan waktu eksekusi c2 N log N Kecepatan eksekusi prosesor 107 instruksi/detik

•

Diketahui: c1  c2 Jika c1=2, c2=50, N = 106 , mana algoritma yang lebih efisien?

Kesimpulan •

Analisa algoritma diperlukan untuk perbandingan algoritma tanpa tergantung spesifikasi mesin

•

Analisa algoritma membantu kita memecahkan masalah sesuai kondisi dan data yang kita hadapi

•

Analisa algoritma bukan alat mutlak untuk memilih algoritma terbaik, tapi membantu memahami perilaku algoritma saat diterapkan di dunia nyata

Terima Kasih

Analisa Kompleksitas Algoritma. Sunu Wibirama

Recommend Documents