Pengantar Analisa Algoritma_budi
-
Upload
umi-mahdiyah -
Category
Documents
-
view
122 -
download
0
description
Transcript of Pengantar Analisa Algoritma_budi
![Page 1: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/1.jpg)
Pengantar Analisa Algoritma
Budi S
![Page 2: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/2.jpg)
Algoritma
Algoritma pertama kali diperkenalkan Oleh Ahli Matematika : Abu Ja’far Muhammad Ibnu Musa Al Khawarizmi.
Seorang Ilmuwan Persia yang menulis kitab Al jabr Muqabala (Rules of restoration and Reduction) sekitar tahun 825 M
![Page 3: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/3.jpg)
APA ITU Algoritma ?
Definisi Urutan langkah-langkah untuk memecahkan
masalah Kamus Besar Bahasa Indonesia:
Algoritma adalah urutan logis pengambilan putusan untuk pemecahan masalah
Algoritma diwujudkan dalam bentuk Program Komputer
![Page 4: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/4.jpg)
Istilah
Program berisi urutan langkah-langkah penyelesaian masalah.
Program ditulis dengan menggunakan bahasa pemrograman.
Orang yang membuat program disebut pemrogram (programmer).
Kegiatan merancang dan menulis program disebut pemrograman.
![Page 5: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/5.jpg)
Ciri Algoritma
1. Finiteness• Jumlah langkah dalam algoritma harus terbatas
2. Definiteness• Setiap langkah harus didefinisikan secara tepat,
tidak boleh membingungkan (ambiguous)3. Input
• Sebuah algoritma memiliki nol atau lebih input yang diberikan kepada algoritma sebelum dijalankan
4. Output• Sebuah algoritma memiliki satu atau lebih output,
yang biasanya bergantung kepada input5. Effectiveness
• Setiap algoritma diharapkan miliki sifat efektif
![Page 6: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/6.jpg)
Algoritma ???
Beberapa masalah dapat diselesaikan dengan algoritma yang bermacam” asal hasilnya sama
Setiap BP punya + - dalam mengimplementasikan algoritma
Setiap programer dapat mengimplementasikan algoritma dengan cara yang berbeda”
algoritma dapat dianalisis efisiensi dan kompleksitasnya, dimana program harus berhenti dalam batas waktu yang wajar (reasonable)
Penilaian algoritma didasarkan pada: Waktu eksekusi (paling utama), d/ mengetahui berapa
banyak resource (time & space) yang diperlukan oleh sebuah algoritma
Penggunaan memori/sumber daya Kesederhanaan dan kejelasan algoritma
![Page 7: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/7.jpg)
Analisa Algoritma….What???
Mengukur jumlah sumber daya (time & space) yang diperlukan oleh sebuah algoritma
Waktu yang diperlukan (running time) oleh sebuah algoritma cenderung tergantung pada jumlah input yang diproses
Algoritma tidak terikat pada platform mesin, OS, BP, kualitas kompilator atau bahkan paradigma pemrograman (mis. Procedural vs Object-Oriented)
![Page 8: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/8.jpg)
Analisa Algoritma….How???
Bagaimana menganalisa algoritma? Jumlah waktu yang digunakan bervariasi
tergantung pada kecepatan mesin sistem operasi (multi-tasking) kualitas kompiler BP yang digunakan
Sehingga kurang memberikan gambaran yang tepat tentang algoritma
![Page 9: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/9.jpg)
Analisa Algortima….Kesimpulan Analisa algoritma tidak mudah dilakukan secara pasti hanya diambil:
Kondisi rata-rata (average case) Kondisi terburuk (worst case) Kondisi baik (best case)
Waktu eksekusi dipengaruhi: Jenis data input Jumlah data input Pemilihan instruksi BP
Faktor” yang menyulitkan analisis, disebabkan: Implementasi instruksi oleh BP berbeda” Ketergantungan algoritma terhadap jenis data Ketidakjelasan algoritma yang diimplementasikan
Langkah” analisis algoritma: Menentukan jenis/sifat data input Mengidentifikasi abstract operation dari data input Menganalisis secara matematis untuk menentukan average case, worst case
dan best case
![Page 10: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/10.jpg)
Analisa Algortima….Kesimpulan
![Page 11: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/11.jpg)
Running Time
Untuk input yang sedikit, beberapa fungsi lebih cepat dibandingkan dengan yang lain
![Page 12: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/12.jpg)
Running Time
Untuk input yang besar, beberapa fungsi running-time sangat lambat - tidak berguna
![Page 13: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/13.jpg)
13
Faster Computer or Algorithm?
What happens when we buy a computer 10 times faster?
T(n) n n’ Change n’/n
10n 1,00 10,000 n’ = 10n 10
20n 500 5,000 n’ = 10n 10
5n log n 250 1,842 10 n < n’ < 10n 7.37
2n2 70 223 n’ = 10n 3.16
2n 13 16 n’ = n + 3 -----
![Page 14: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/14.jpg)
Desain Algoritma: Contoh1
Problem: Pandang barisan n buah bilangan
Ingin dicari bilangan x apakah ada pada sederetan bilangan tersebut. Kalau ada, x berada pada index ke berapa.
Algoritma: Input: Array A dengan n elemen bilangan dan bilangan x yang dicari.
Output: Bilangan bulat non negatif j yang merupakan letak/index x
dalam array A Menghasilkan j=-1 bila x tidak ada di A
Langkah-langkah: ?
a1, a2, a3, ... , an
![Page 15: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/15.jpg)
Desain Algoritma: Contoh2
Pandang sederetan n buah bilangan
Akan dicari bilangan max yang merupakan bilangan terbesar dari n buah sederetan bilangan tersebut.
Algoritma Input: Array A dengan n elemen bilangan Output: Bilangan max=maksimum( ) Langkah-langkah:
CariMaximal(A,n,max) {
1. max=A[0];
2. for(i=1; i<n ; i++)
3. if (max<A[i]) max=A[i];
4. return max;
}
a1, a2, a3, ... , an xn
a1, a2, a3, ... , an xn
![Page 16: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/16.jpg)
Analisis Algoritma: mengapa
Suatu permasalahan memungkinkan untuk diselesaikan dengan lebih dari satu algoritma (pendekatan)
Bagaimana kita ‘memilih’ satu yang ‘terbaik’ diantara beberapa algoritma tersebut. Bagaimana kita mengukur ‘efisiensi’ dari algoritma tersebut?
So, diperlukan analisis algoritma
![Page 17: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/17.jpg)
Analisis Algoritma: definisi
Merupakan suatu metoda untuk mengetahui unjuk kerja (performansi) suatu algoritma
Dapat berupa membandingkan biaya komputasi dari dua (atau lebih) algoritma untuk suatu permasalahan yang sama, atau untuk memperkirakan apakah solusi yang kita berikan dapat memenuhi kendala-kendala dari permasalahannya.
![Page 18: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/18.jpg)
Analisis algoritma: apa yang dianalisis Kebenaran Banyaknya kerja yang dilakukan Banyaknya memori yang dipakai Kesederhanaan Optimalitas
![Page 19: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/19.jpg)
Kebenaran
Suatu algoritma dikatakan benar, bila setiap diberikan input yang valid maka algoritma tersebut akan menghasilkan output yang diinginkan.
![Page 20: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/20.jpg)
Uji Kebenaran
Pembuktian Jika preconditions/input dipenuhi, Maka postconditions/output benar, Ketika algoritma berhenti.
Contoh?
![Page 21: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/21.jpg)
Uji Kebenaran: Contoh
Akan ditunjukan bahwa algoritma CariMaximal merupakan algoritma yang benar.
CariMaximal(A,n,max) {
1. max=A[0];
2. for(i=1; i<n ; i++)
3. if (max<A[i]) max=A[i];
4. return max;
}
![Page 22: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/22.jpg)
Bukti:
Setelah melakukan pengerjaan statemen for(i=1; i<n ; i++), bilangan yang berada pada variabel max adalah bilangan terbesar dari A[0], A[1], ..., A[n-1]. Ini akan kita buktikan kebenarannya dengan menggunakan bukti induksi.Basis induksi: ambil i = 1 (dua elemen),Jika A[0] > A[1] maka max = A[0], selainnya max = A[1]. Dengan demikian max adalah terbesar dari A[0] dan A[1].Langkah asumsi : diasumsikan benar untuk i=k, yaitu max adalah bilangan terbesar dari A[0], A[1], ..., A[k].Akan dibuktikan benar untuk i=k+1.
![Page 23: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/23.jpg)
Bukti(lanjutan)
Pada saat mencapai baris 2 dengan i=k+1 dan kemudian mengerjakan baris 3 sebagai berikut. if (max<A[k+1]) max=A[k+1]; Ingat bahwa (dari langkah asumsi) sampai disini variabel
max berisi nilai terbesar dari A[0], A[1], ..., A[k]. Bila tes ekspresi pada baris 3 bernilai benar maka max = A[k+1], sehingga didapat max adalah nilai terbesar dari A[0], A[1], ..., A[k+1]. Dan apabila tes pada baris 3 tidak benar maka max masih tetap nilai terbesar dari A[0], A[1], ..., A[k+1].
Jadi secara induksi algoritma ini terbukti benar.
![Page 24: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/24.jpg)
Banyaknya kerja yang dilakukan
Mengukur efisiensi suatu algoritma berdasarkan banyaknya kerja yang dilakukan algoritma jika diberikan ‘ukuran’ input (yang biasanya besar), karena running-time suatu algoritma sebagian besar tergantung pada ukuran input.
Dihitung untuk best case, worst case dan average case
Pertimbangan utama ketika mengestimasi performansi suatu algoritma adalah jumlah ‘operasi dasar’ (basic operation) yang diperlukan untuk oleh algoritma untuk memproses suatu input dengan ukuran (size)
![Page 25: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/25.jpg)
Operasi dasar: contohNo Permasalahan Operasi Yang Diukur Ukuran Input
1 Cari x dalam array A[1], A[1], ... A[n]
Pembandingan Banyaknya elemen, n.
2 Pengurutan elemen array
A[0], A[1], ..., A[n-1]
Pembandingan Banyaknya elemen, n.
3 Penjumlahan matrik Penjumlahan Banyaknya baris m dan banyaknya kolom n.
4 Perkalian matrik Perkalian, dan penjum-lahan (bila perlu)
Banyaknya baris m, banyaknya kolom p dan n.
5 Penyelesaian sistem persamaan linier
Perkalian,
dan penjumlahan (bila perlu)
Banyaknya persamaan atau variabel, n.
6 Pengunjungan node pada pohon biner
Pointer Banyaknya node pada pohon biner.
Anxn xnx1 bnx1
Cmxn Amxn Bmxn
Cmxn Amxp Bpxn
![Page 26: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/26.jpg)
Banyak Kerja yang dilakukan: Contoh
Algoritma SequentialSearch dengan input berupa array A[0], A[1], ..., A[n] dan bilangan yang dicari x. Akan terjadi kemungkinan - kemungkinan sebagai berikut.Apabila nilai x sama dengan nilai A[0], maka algoritma akan melakukan kerja pembandingan (mencapai kontrol pada baris 2 dan mebandingkan x dengan A[0]) sebanyak 1 kali. Keadaan terbaik (best case)Apabila nilai x sama dengan nilai A[1], maka algoritma akan melakukan kerja pembandingan sebanyak 2 kali. Apabila nilai x sama dengan nilai A[2], maka algoritma akan melakukan kerja pembandingan sebanyak 3 kali…. dan seterusnya.Apabila nilai x tidak ada di array A, maka algoritma akan melakukan kerja pembandingan sebanyak n kali. Ini merupakan kasus terburuk (worst case).
![Page 27: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/27.jpg)
27
Asymptotic Analysis: Big-oh
Definition: For T(n) a non-negatively valued function, T(n) is in the set O(f(n)) if there exist two positive constants c and n0 such that |T(n)| <= c|f(n)| for all n > n0.
T(n) : running time
Usage: The algorithm is in O(n2) in [best, average, worst] case.
Meaning: For all data sets big enough (i.e., n>n0), the algorithm always executes in less than c|f(n)| steps in [best, average, worst] case.
![Page 28: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/28.jpg)
28
Big-oh Notation (cont)
Big-oh notation indicates an upper bound.
Example: If T(n) = 3n2 then T(n) is in O(n2).
Wish tightest upper bound:While T(n) = 3n2 is in O(n3), we prefer O(n2).
![Page 29: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/29.jpg)
29
Big-Oh Examples
Example 2: T(n) = c1n2 + c2n in average case.
|c1n2 + c2n| <= |c1n2 + c2n2| <= (c1 + c2)|n2|for all n > 1.
T(n) <= c|n2| for c = c1 + c2 and n0 = 1.
Therefore, T(n) is in O(n2) by the definition.
Example 3: T(n) = c. We say this is in O(1).
![Page 30: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/30.jpg)
30
A Common Misunderstanding
“The best case for my algorithm is n=1 because that is the fastest.” WRONG!
Big-oh refers to a growth rate as n grows to .Best case is defined as which input of size n is
cheapest among all inputs of size n.
![Page 31: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/31.jpg)
31
Big-Omega
Definition: For T(n) a non-negatively valued function, T(n) is in the set (g(n)) if there exist two positive constants c and n0 such that |T(n)| >= c|g(n)| for all n > n0.
Meaning: For all data sets big enough (i.e., n > n0), the algorithm always executes in more than cg(n) steps.
Lower bound.
![Page 32: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/32.jpg)
32
Big-Omega Example
T(n) = c1n2 + c2n. For c2 and c2 > 0
|c1n2 + c2n| >= |c1n2| >= c1 |n2| for all n > 1.
|T(n)| >= c|n2| for c = c1 and n0 = 1.
Therefore, T(n) is in (n2) by the definition.
We want the greatest lower bound.
![Page 33: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/33.jpg)
33
Theta Notation
When big-Oh and meet, we indicate this by using (big-Theta) notation.
Definition: An algorithm is said to be (h(n)) if it is in O(h(n)) and it is in (h(n)).
![Page 34: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/34.jpg)
34
A Common Misunderstanding
Confusing worst case with upper bound.
Upper bound refers to a growth rate.
Worst case refers to the worst input from among the choices for possible inputs of a given size.
![Page 35: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/35.jpg)
NOTASI Big-Oh/O (1)
Fungsi: Digunakan sebagai bahasa untuk membahas efisiensi
dari sebuah algoritma: log n, linier, n log n, n2, n3, ... digunakan untuk merepresentasikan laju pertumbuhan
(growth rate) Dari hasil run-time, dapat kita buat grafik dari waktu
eksekusi dan jumlah data Mrkfungsi yang berkaitan dengan kelajuan proses daripada
kelajuan pertambahan dataT(n) = O(f(n))if ada konstan c dan no sedemikian rupa thenT(n) ≤ c.f(n) untuk n ≥ no O(f(n)) nilai maksimum dari c.f(n)
c/ If f(n) = 2n2 Then T(n) = O(n2)
If f(n) = 4n2 + 7n + 3 Then T(n) = O(n3)
![Page 36: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/36.jpg)
36
Big-Oh - Contoh
T(n) = c1n2 + c2n in average case.
c1n2 + c2n <= c1n2 + c2n2 <= (c1 + c2)n2 for all n > 1.
T(n) <= cn2 for c = c1 + c2 and n0 = 1.
Therefore, T(n) is in O(n2) by the definition.
![Page 37: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/37.jpg)
NOTASI Big-Oh/O (3) c/ program-1
sum=0;for (i=0; i<n; i++)
sum=sum+a[i];Penghitungan eksekusi:sum = 0 dieksekusi 1 kalii = 0 dieksekusi 1 kalii < n diekseklusi n kalii++ dieksekusi n kalisum = sum + a[i] dieksekusi n kali
----------------------2 + 3n kali Jadi T(n) = O(n)
Function Name c Constant log N Logarithmic log2 N Log-squared N Linear N log N N log N N2 Quadratic N3 Cubic 2N Exponential N! Factorial
![Page 38: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/38.jpg)
NOTASI Big-Oh/O (4) c/ program-2
sum=0;for (i=0; i<n; i++)
for (j=0; j<n; j++)sum= sum+a[j];
Penghitungan eksekusi:sum = 0 dieksekusi 1 kalii = 0 dieksekusi 1 kalii < n dieksekusi n kalii++ dieksekusi n kalij = 0 dieksekusi 1 kalij < n dieksekusi n × n kalij++ dieksekusi n × n kalisum = sum + a[ j ] dieksekusi n × n kali
--------------------------- 3 + 2n + 3n2 kali
![Page 39: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/39.jpg)
KLASIFIKASI ALGORITMA (1)
T(n)=c Jika sebagian besar instruksi pada program hanya dieksekusi
constant/ sekali Bersifat konstan, tidak bergantung pada parameter/n data yang
diolah Merupakan algoritma paling ideal
c/ void hitung(){
a=2;b=2;c=a+b;
}
![Page 40: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/40.jpg)
KLASIFIKASI ALGORITMA (2)
T(n)=O(n) Waktu eksekusinya sebanding/sama dengan jumlah data Setiap data input hanya diolah secara sederhana, c/ untuk
operasi + - x : Kondisi optimal yang dicari dalam membuat algoritma
c/
for (int i=0; i<n; i++)
a[i]=0;
![Page 41: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/41.jpg)
KLASIFIKASI ALGORITMA (3)
Waktu eksekusi berbading dengan kwadrat jumlah data, m/: Jika n=10 waktu eksekusinya 100 Jika n=20 waktu eksekusinya 400
Biasanya timbul karena setiap data dieksekusi 2 kali, misal dlm nested loop
c/ Algoritma Bublesortfor(int i=0; i<n; i++)
for (int j=0; j<m; j++)a[i,j]=0;
d/ perhitungan: Loop luar dieksekusi n kali Loop dalam dieksekusi m kali Total eksekusi = n × m kali
)()( 2nOnT
![Page 42: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/42.jpg)
KLASIFIKASI ALGORITMA (5)
Untuk algoritma yang mengolah setiap data input 3x c/ pada nested loop Algoritma semacam ini sebisa mungkin dihindari c/
for (i=0; i<n; i++)
for (j=0; j<n; j++)
for (k=0; k<n; k++)
a[i,j,k]=0;
)()( 3nOnT
![Page 43: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/43.jpg)
KLASIFIKASI ALGORITMA (4)
T(n)=O(log n) Waktu eksekusi sebanding dengan algoritma dari n-data m/ n-data menjadi 2 kali semula berarti waktu proses
bertambah 1 unit; jika 1000x bertambah 10 unit, jika 1000000x berarti 20 unit
Biasanya untuk algoritma yang memecah masalah besar kedalam sub masalah yang lebih kecil
c/ Algoritma binary search dan algoritma fungsi rekursif T(n)=O(n log n)
Bersifat linier dan logaritmis Untuk algoritma yang memecah masalah besar menjadi
sub-masalah yang lebih kecil dan diselesaikan secara terpisah, kemudian hasilnya digabungkan.
Contoh : Quicksort
![Page 44: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/44.jpg)
KLASIFIKASI ALGORITMA (6)
Pada implementasinya, algoritma kadang-kadang memiliki Big-Oh yang merupakan kombinasi dari klasifikasi dasar tersebut
Perancangan algoritma yang memiliki Big-Oh baik tetapi rumit tidak selalu menguntungkan apabila jumlah data inputnya hanya sedikit
Nilai Big-Oh adalah nilai worst case, sehingga dalam implementasinya biasanya tidak mencapai nilai setinggi itu
n log n n log n n2 n3
10 3 30 100 1000
100 6 600 10000 100000
1000 9 9000 1000000 1000000
10000 13 130000 100 juta 1 trilyun
100000 16 1600000 10 milyard 100 trilyun
![Page 45: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/45.jpg)
Aturan Algoritma:1. For Loop (perulangan) Waktu eksekusi pada for loop, maksimum sebanyak
waktu eksekusi statement” yang ada di dalam loop dikalikan banyaknya iterasi
c/for (a=0; a<n; a++){
m=a+b;n=c+d;
} Waktu eksekusi = 2 x n kali Jadi T(n) = O(n)
![Page 46: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/46.jpg)
Aturan Algoritma:2. Nested for loop (perulangan bersarang)
Dianalisis dari loop terdalam kemudian keluar Waktu eksekusi total sebuah statement adalah waktu
eksekusi statement tsb dikalikan hasil kali dari banyaknya iterasi semua loop yang ada diluarnya
c/
for(int i=0; i<n; i++)
for (int j=0; j<m; j++)
a[i,j]=0; a[i,j] akan dieksekusi sebanyak (m x n) kali. Jadi T(n) = O(n2)
![Page 47: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/47.jpg)
Aturan Algoritma:3. Consecutive Statement (statement yang berurutan)
Untuk statement yang berurutan, waktu eksekusinya adalah jml dari masing-masing statement
Berdasarkan pengertian Big-OH, hal tsb akan diambil nilai yang terbesar
c/ (1) for(int k=0; k<10; k++)(2) x[k]=0;(3) for(int i=0; i<n; i++)(4) for (int j=0; j<m; j++)(5) a[i,j]=0;
Jadi T(n) = T1(n) + T2(n)+T3(n) = O(n3)
)()( 21 nOnT
)()( 22 nOnT
![Page 48: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/48.jpg)
Aturan Algoritma:
4. if else Total waktu eksekusi adalah waktu test ditambah waktu yang
terbesar dari eksekusi Statemen1 atau Statemen2 c/
(1) if (a<10)(2) {(3) m=a+b;(4) n=c+d;(5) }(6) else(7) {(8) for (i=0; i<10; i++)(9) x=x+i;(10) } u/ baris 1-10 dengan rentang waktu tes=1-10 Jadi total waktu eksekusi adalah 1 + 10 = 11 Jadi T(n) = O(n)
![Page 49: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/49.jpg)
Big-Oh Rules (1)
Ekspresi matematika untuk menyatakan tingkat laju pertumbuhan relatif: DEFINITION: (Big-Oh) T(N) = O(F(N)) jika ada
konstan positif c dan N0 sehingga T(N) c F(N)
untuk N N0.
DEFINITION: (Big-Omega) T(N) = (F(N)) jika ada konstan c dan N0 sehingga T(N) c F(N)
untuk N N0
DEFINITION: (Big-Theta) T(N) = (F(N)) jika dan hanya jika T(N) = O(F(N)) dan T(N) = (F(N)).
DEFINITION: (Little-Oh) T(N) = o(F(N)) jika dan hanya jika T(N) = O(F(N)) dan T(N) (F(N)).
![Page 50: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/50.jpg)
Big-Oh Rules (2) Arti dari beberapa fungsi tingkat laju.
Jika ada lebih dari satu parameter, maka aturan tersebut berlaku untuk setiap parameter. 4 n log(m) + 50 n2 + 500 m + 1853
O(n log(m) + n2 + m) 4 m log(m) + 50 n2 + 500 m + 853
O(m log(m) + n2)
T(N) = O(F(N)) Growth of T(N) is growth of F(N) T(N) = (F(N)) Growth of T(N) is growth of F(N) T(N) = (F(N)) Growth of T(N) is = growth of F(N) T(N) = o(F(N)) Growth of T(N) is growth of F(N)
![Page 51: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/51.jpg)
Panduan Running Time (detik)
![Page 52: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/52.jpg)
Contoh Algoritma Mencari dua titik yang memiliki jarak terpendek dalam sebuah
bidang koordinat XY Masalah dalam komputer grafis Algoritma brute force:
hitung jarak dari semua pasangan titik cari jarak yang terpendek
Jika jumlah titik adalah n, maka jumlah semua pasangan n*(n-1)/ 2 Orde-nya: O(n2) – kuadratik Ada solusi yang O(n log n) bahkan O(n) dengan cara algoritma lain
Tentukan apakah ada tiga titik dalam sebuah bidang yang segaris (colinier) Algoritma brute force:
periksa semua tripel titik yang terdiri dari 3 titik Jumlah pasangan: n * (n - 1) * (n - 2) / 6 Orde-nya: O(n3) - kubik. Sangat tidak berguna untuk 10.000 titik Ada algoritma yang kuadratik
![Page 53: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/53.jpg)
04/22/23 53
Studi Kasus
Mengamati sebuah masalah dengan beberapa solusi
Masalah Maximum Contiguous Subsequence Sum Diberikan (angka integer negatif A1, A2, …, AN)
cari nilai maksimum dari (Ai + Ai+1 + …+ Aj ) maximum contiguous subsequence sum=0
jika semua integer adalah negatif
![Page 54: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/54.jpg)
Brute Force Algorithma (1) Algoritma:
Hitung jumlah dari semua sub-sequence yang mungkin
Cari nilai maksimumnya Contoh:
jumlah subsequence (start, end)
• (0, 0), (0,1), (0,2), …, (0,5)• (1,1), (1,2), …, (1, 5)• …• (5,5)
![Page 55: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/55.jpg)
04/22/23 55
Brute Force Algorithm (2)
public static int maxSubSum1( int [] A ) { int maxSum = 0; for(int ii = 0; ii < A.length; ii++) { for( int jj = ii; jj < A.length; jj++) { int thisSum= 0; for(int kk = ii; kk <= jj; kk++) thisSum += A[kk]; if( thisSum > maxSum ) maxSum = thisSum; } } return maxSum ; }
•sum [ii, jj] = sum [ii, jj – 1] + Ajj
![Page 56: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/56.jpg)
04/22/23 56
Brute Force Algorithma (3) Analisa:
Iterasi (kk) sebanyak N dalam iterasi (jj) sebanyak N dalam iterasi (ii) sebanyak N artinya: O(N3), atau algoritma kubik.Slight over-estimate yang dihasilkan dari perhitungan iterasi yang kurang dari N adalah tidak terlalu penting (kk <= jj)
Running Time:Untuk N = 100, waktu sebenarnya adalah 0.47 detik pada sebuah komputerDapat menggunakan informasi tersebut, untuk memperkirakan waktu untuk input yang lebih besar:
T(N) = cN 3T(10N) = c(10N)3 = 1000cN 3 = 1000T(N)
Ukuran input meningkat dengan kelipatan 10 kali, yang artinya meningkatkan running time dengan kelipatan 1000 kali. Untuk N = 1000, perkiraan waktu 470 detik. (waktu sebenarnya 449 detik).Untuk N = 10.000, perkiraan waktu 449000 detik (6 hari).
![Page 57: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/57.jpg)
04/22/23 57
Brute Force Algorithma (4) Bagaimana memperbaikinya?
Membuang sebuah iterasi; Tidak selalu bisa Dalam contoh sebelumnya dimungkinkan:
iterasi paling dalam (kk) tidak diperlukan karena informasi nya terbuang
Nilai thisSum untuk nilai jj selanjutnya dapat dengan mudah diperoleh dari nilai thisSum yang sebelumnya: Yang diperlukan: Aii + A ii+1 + … + A jj-1 + Ajj
Yang telah dihitung: Aii +A ii+1 + …+ A jj-1
Yang dibutuhkan adalah yang telah dihitung + Ajj
Dengan kata lain:
• sum [ii, jj] = sum [ii, jj – 1] + Ajj
![Page 58: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/58.jpg)
Contoh Algoritma Brute Force
1. Menghitung an (a > 0, n adalah bilangan bulat tak-negatif) an = a x a x … x a (n kali) , jika n > 0 = 1 , jika n = 0
Algoritma: kalikan 1 dengan a sebanyak n kali
![Page 59: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/59.jpg)
2. Menghitung n! (n bilangan bulat tak-negatif)
n! = 1 × 2 × 3 × … × n , jika n > 0
= 1 , jika n = 0
Algoritma:
kalikan n buah bilangan, yaitu 1, 2, 3, …, n, bersama-sama
Contoh Algoritma Brute Force
![Page 60: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/60.jpg)
Contoh Algoritma Brute Force
3. Mengalikan dua buah matrik yang berukuran n × n
Misalkan C = A × B dan elemen-elemen matrik dinyatakan sebagai cij, aij, dan bij
Deklarasi i, j, k, n: integer input A, B: matrik output C: matriksAlgoritmahitung setiap elemen hasil perkalian satu per satu, dengan cara mengalikan dua vektor yang panjangnya n. for (i=0; i<n; i++) for (j=0; j<n; j++) C[i,j]=0 for (k=0; k<n; k++) C[i,j]=C[i,j]+A[i,k]*B[k,j]
n
kkjiknjinjijiij
babababac1
2211
![Page 61: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/61.jpg)
Contoh Algoritma Brute Force4. Menemukan semua faktor dari bilangan bulat n selain dari 1
dan n itu sendiri.
Definisi: Bilangan bulat a adalah faktor dari bilangan bulat b jika a habis membagi b
Deklarasik:integerinput n:integer
Algoritmak=0ketemu=falsefor (k=2; k<n-1; k++) if n mod k=0 then
s.o.p(k)
![Page 62: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/62.jpg)
Contoh Algoritma Brute Force5. Mencari elemen terbesar atau terkecil
Persoalan: Diberikan sebuah himpunan yang beranggotakan n buah bilangan bulat. Bilangan-bilangan bulat tersebut dinyatakan sebagai a1, a2, …, an. Carilah elemen terbesar di dalam himpunan tersebutDeklarasi
k:integerinput a1,a2….an:integeroutput maks:integer
Algoritmamaks=a1;for (k=2; k<n; k++) if a[k]>maks then
maks=a[k];Kompleksitas algoritma ini adalah O(n)
![Page 63: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/63.jpg)
Contoh Algoritma Brute Force
6. Sequential Search
Persoalan: Diberikan n buah bilangan bulat yang dinyatakan sebagai a1, a2, …, an. Carilah apakah x terdapat di dalam himpunan bilangan bulat tersebut. Jika x ditemukan, maka lokasi (indeks) elemen yang bernilai x disimpan di dalam peubah idx. Jika x tidak terdapat di dalam himpunan tersebut, maka idx diisi dengan nilai 0
Deklarasik,x:integerinput a1,a2….an:integeroutput idx:integer
Algoritma k=1 while(k<n)and(a[k]!=x) do k=k+1 endwhile if a[k]=x then idx=k else idx=0 endifKompleksitas algoritma ini adalah O(n)
![Page 64: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/64.jpg)
Contoh Algoritma Brute Force
7. Bubble Sort
• metode yang paling bagus dalam memecahkan masalah pengurutan algoritma bubble sort
• Alur mengurutkan tabel L[1…n], sehingga terurut naik; dengan inputan (tabel L yang sudah didefinisikan nilai”nya); output (tabel L yang terurut naik L[1]<=L[2]…<=L[n]Deklarasi
i,k,n,temp:integerinput/output tabel L: integer
Algoritmafor (i=1; i<n-1; i++)
for (k=n; k<n-1; i++) if L[k]<L[k-1] then temp=L[k] L[k]=L[k-1]
L[k-1]=tempKompleksitas algoritma ini adalah O(n2)
![Page 65: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/65.jpg)
Contoh Algoritma Brute Force
8. Menentukan bilangan prima
Persoalan: Diberikan sebuah bilangan bilangan bulat positif. Ujilah apakah bilangan tersebut merupakan bilangan prima atau bukan.
Next Lanjut:
akan kita terapkan di materi tentang searching; Sorting & Rekursif
![Page 66: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/66.jpg)
04/22/23 66
The Better Algorithma (1) Analisa:
Dengan logika yang sama, Saat ini running time adalah quadratic, or O(N2)Perkirakan waktu eksekusi untuk input berukuran ribuan. Algoritma ini masih dapat digunakan untuk ukuran input 10 ribu Running Time:Untuk N = 100, waktu sebenarnya adalah 0.011 detik pada sebuah komputerPerkirakan waktu sebenarnya untuk input lebih besar:
T(N) = cN 2
T(10N) = c(10N)2 = 100cN 2 = 100T(N)Input diperbesar dengan kelipatan 10 artinya running time akan membesar dengan kelipatan 100
u/ N = 1000, perkiraan running time 1.11 detik (waktu sebenarnya 1.12 detik)u/ N = 10,000, perkiraan 111 detik (= actual)
![Page 67: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/67.jpg)
04/22/23 67
The Better Algorithma (2) public static int maxSubSum2( int [ ] A ) { int maxSum = 0; for( int ii = 0; ii < A.length; ii++ ) { int thisSum = 0; for( int jj = ii; jj < A.length; jj++ ) { thisSum += A[jj]; if( thisSum > maxSum ) maxSum = thisSum; } } return maxSum ; }
![Page 68: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/68.jpg)
04/22/23 68
Algoritma Rekursif (1) Gunakan pendekatan divide-and-conquer :
Membagi (divide) permasalahan ke dalam bagian yang lebih kecil
Menyelesaikan (conquer) masalah per bagian secara recursive
Menggabung penyelesaian per bagian menjadi solusi masalah awal
Urutan dengan nilai jumlah terbesar kemungkinan berada pada: terletak di setengah input awal terletak di setengah input akhir. berawal disetengan input awal dan berakhir di setengah
input akhir. Hitung ketiga kemungkinan tersebut. Cari yang lebih
besar. Kedua kemungkinan pertama dapat dengan mudah
dihitung secara rekursif.
![Page 69: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/69.jpg)
04/22/23 69
Algoritma Rekursif (2)
dapat dilakukan dengan dua iterasi; lihat program
kemungkinan ketika berasal dari penjumlahan dua bagian, bagian pertama berawal pada setengah bagian input pertama berakhir di tengah. Bagian kedua berasal dari urutan index setengah +1 hingga setengah bagian input akhir.bagian pertama gunakan iterasi dari kanan-ke-kiri (right-to-left) mulai dari element terakhir pada setengah input awal.bagian kedua, gunakan iterasi dari kiri-ke-kanan, (left-to-right) mulai dari awal setengah input akhir.
![Page 70: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/70.jpg)
04/22/23 70
Algoritma Rekursif (3)
Pastikan dalam rekursif program anda ada base case untuk mengatasi zero-element arrays.
Gunakan method “driver” yang public (method rekursif dibuat private)
Aturan Rekursif : Memiliki base case Membuat progress menuju ke base case Asumsikan bahwa panggilan rekursif bekerja
dengan baik. Hindari menghitung sebuah penyelesaian
dua kali.
![Page 71: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/71.jpg)
Algoritma Rekursif (4)
private int maxSumRec (int[] a, int left, int right) { int center = (left + right) / 2; if(left == right) { // Base case return a[left] > 0 ? a[left] : 0; } int maxLeftSum = maxSumRec (a, left, center);
int maxRightSum = maxSumRec (a, center+1, right); for(int ii = center; ii >= left; ii--) {
leftBorderSum += a[ii]; if(leftBorderSum > maxLeftBorderSum) maxLeftBorderSum = leftBorderSum; }
4 -3 5 -2 -1 2 6 -24* 0 3 -2 -1 1 7* 5
Tengah-tengah
![Page 72: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/72.jpg)
Algoritma Rekursif (5)
for(int jj = center + 1; jj <= right; jj++) { rightBorderSum += a[jj]; if(rightBorderSum > maxRightBorderSum) maxRightBorderSum = rightBorderSum; } return max3 (maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);}// publicly visible routine (a.k.a driver function)public int maxSubSum (int [] a) { return maxSumRec (a, 0, a.length-1);}
![Page 73: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/73.jpg)
04/22/23 73
Algoritma Rekursif (6)Analisa
Misalkan T( N ) adalah waktu untuk menyelesaikan masalah dengan ukuran input N.
maka T( 1 ) = 1 (1 adalah quantum time unit ketika memproses base case; ingat konstanta tidak terlalu penting. ).
T( N ) = 2 T( N / 2 ) + N Dua buah pemanggilan rekursif, masing-masing
berukuran N / 2. Waktu yang dibutuhkan untuk menyelesaikan masing-masing-nya adalah T( N / 2 )
Kasus ketiga membutuhkan O( N ) .
![Page 74: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/74.jpg)
04/22/23 74
Bottom Line Algoritma
T(1) = 1 = 1 * 1T(2) = 2 * T(1) + 2 = 4 = 2 * 2T(4) = 2 * T(2) + 4 = 12 = 4 * 3T(8) = 2 * T(4) + 8 = 32 = 8 * 4T(16) = 2 * T(8) + 16 = 80 = 16 * 5T(32) = 2 * T(16) + 32 = 192 = 32 * 6T(64) = 2 * T(32) + 64 = 448 = 64 * 7
T(N) = N(1 + log N) = N + N log N = O(N log N)
![Page 75: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/75.jpg)
04/22/23 75
Bottom Line Algoritma Setiap algoritma rekursif yang menyelesaikankan
permasalahan dengan membagi dua permasalahan kemudian melakukan proses linear (menggabung atau memecah) akan selalu O( N log N ) karena analisa yang sama tetap berlaku
Algoritma yang O( N log N ) adalah jauh lebih baik dibanding quadratic
Tapi masih belum lebih baik dibanding O( N ), namun tidak terlalu jauh berbeda
![Page 76: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/76.jpg)
04/22/23 76
Algoritma linear (1)
Algoritma Linear merupakan yang terbaik. Ingat: linear artinya O( N ). Running time yang linear selalu sebanding
dengan ukuran input. Sulit untuk membuat algoritma yang lebih baik dari linear (kecuali ada rumusan tertentu).
Jika input membesar dengan kelipatan 10, maka running time juga hanya akan membesar dengan kelipatan yang sama.
![Page 77: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/77.jpg)
Algoritma linear (2)
Ai,j adalah kumpulan bilangan mulai dari
urutan i hingga urutan j.
Si,j adalah dari kumpulan bilangan tersebut.
Theorema: Untuk Ai,j dengan Si,j < 0. Jika q >
j, maka Ai,q bukanlah deretan terurut yang
terbesar. Bukti:
Si,q = Si,j + Sj+1,q
Si,j < 0 Si,q < Sj+1,q
![Page 78: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/78.jpg)
Algoritma Linear (3)program1static public int maximumSubSequenceSum3 (int a[]) { int maxSum = 0; int thisSum = 0; for (int jj = 0; jj < a.length; jj++) { thisSum += a[jj]; if (thisSum > maxSum) { maxSum = thisSum; } else if (thisSum < 0) { thisSum = 0; } } return maxSum;}
![Page 79: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/79.jpg)
Algoritma Linear (3) program2static public int
maximumSubSequenceSum3b (int a[])
{
int thisSum = 0, maxSum = 0;
for (int ii = 0; ii < a.length; ii++) {
thisSum = Max(0, a[ii] + thisSum);
maxSum = Max(thisSum, maxSum);
}
return maxSum;
}
![Page 80: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/80.jpg)
04/22/23 80
Algoritma Logaritme Definisi Formal
Untuk setiap B, N > 0, logB N = K, if B K = N. Jika (base) B diabaikan, maka default-nya adalah 2 dalam
konteks ilmu komputer (binary representation). c/ log 32 = 5 (karena 25 = 32); log 1024 = 10; log 1048576
= 20; log 1 milyard = sekitar 30 logaritme berkembang jauh lebih lambat dari N dan
lebih lambat dari akar kuadrat dari N. Sebuah algoritma adalah O( log N ) jika
membutuhkan waktu konstan untuk membagi input permasalahan dan mengerjakan masing-masing-nya secara rekursif. (biasanya 1/2).
Penjelasan: Akan terjadi sebanyak log N dari proses konstan tersebut.
![Page 81: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/81.jpg)
04/22/23 81
Contoh Algoritma Logaritme
Mencari bits dalam binary number Berapa banyak bits dibutuhkan untuk
merepresentasikan bilangan bulat? perulangan
Mulai dari X = 1, berapa kali X harus dikalikan dua agar mendekati nilai N?
Mulai dari X = N, jika N dibagi dua terus menerus, berapa kali iterasi agar membuat N lebih kecil atau sama dengan 1 (Halving rounds up).
![Page 82: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/82.jpg)
04/22/23 82
Linear Search
Bila diberikan sebuah bilangan bulat X dan sebuah array A, kembalikan posisi X dalam A atau sebuah tanda bila tidak ada X dalam A. Jika X muncul lebih dari sekali, kembalikan posisi manapun. Array A tidak perlu diubah.
Jika array input tidak terurut, solusinya adalah menggunakan linear search. Running times: pencarian tidak berhasil: O( N ); setiap element
diperiksa pencarian berhasil:
• Worst case: O( N ); setiap element diperiksa• Average case: O( N ); setengah bagian
diperiksa
![Page 83: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/83.jpg)
04/22/23 83
Binary Search (1)
Lihat bilangan ditengah (asumsi array terurut dari kiri ke kanan) Kasus 1: Jika X lebih kecil dari bilangan
ditengah, maka hanya perlu lihat sub array bagian kiri.
Kasus 2: Jika X lebih besar dari bilangan ditengah, maka hanya perlu lihat sub array bagian kanan
Kasus 3: Jika X sama dengan bilangan ditengah, maka selesai.
Base Case: Jika input sub array kosong, X tidak ditemukan.
![Page 84: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/84.jpg)
Binary Search (2)public static int binarySearch (Comparable [ ] a, Comparable x ) throws ItemNotFound{ int low = 0; int high = a.length - 1; int mid;
while( low <= high ) { mid = (low + high) / 2; if (a[mid].compareTo (x) < 0) { low = mid + 1; } else if (a[mid].compareTo (x) > 0) { high = mid - 1; } else { return mid; } } throw new ItemNotFound( "BinarySearch fails" );}
![Page 85: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/85.jpg)
04/22/23 85
Binary Search (3)
Dapat melakukan satu perbandingan tiap iterasi dari pada dua iterasi dengan cara menggantikan base case: Save the value returned by a[mid].compareTo (x)
Average case dan worst case dalam algoritma hasil revisi adalah sama : 1 + log N perbandingan (dibulatkan). Contoh: If N = 1,000,000, maka 20 bilangan dibandingkan.
Sequential search akan lebih banyak 25,000 kali dalam kondisi rata-rata (average case).
![Page 86: Pengantar Analisa Algoritma_budi](https://reader033.fdokumen.site/reader033/viewer/2022061519/55cf93f1550346f57b9eda3d/html5/thumbnails/86.jpg)
Tugas:
Int select (int a[], int k, int n){
int I, j, mini, tmp;for (i=0; i<k; i++){
mini=i;for (j=i+1; j<n; j++){
if (a[j]<a[mini])mini=j;
temp=a[i];a[i]=a[mini];a[mini]=tmp;
}return a[k-1];
}}