Analisis Algoritma. Jimmy Tirtawangsa. Universitas Telkom 2014

Analisis Algoritma Jimmy Tirtawangsa

Universitas Telkom 2014

Daftar Isi (1) Motivasi (2) Kompleksitas

dan Optimalitas

(3) Struktur data (4) Teknik2 analisis algoritma (5) Struktur graf (6) Problem Sulit/Intraktabel

Kompleksitas dan Optimalitas Saat menghadapi problem komputasi: (1) Cari sebuah solusi algoritmik (a) Cari ide, buat algoritma (b) Buktikan algorima sesuai (c) Analisis kompleksitasnya

(2) Kurang puas? Perbaikan solusi (3) Apakah solusi optimal? (4) Kiat apa jika optimal juga tidak cukup. Menembus batas

Contoh Ideal: Pengurutan Data ●

Satu problem komputasi yang sangat banyak manfaatnya

●

Sudah diselidiki oleh banyak orang

●

Berbagai solusi telah dikembangkan

●

Optimalitas solusi sudah terbukti

●

Berbagai cara untuk mengingkari batas optimal juga banyak dilakukan

Pengurutan Data ●

●

●

Masukan: Sekumpulan data tersimpan dalam array Keluaran: Salah satu permutasi data tersebut, dimana data terurut monotonik membesar dari indek pertama s.d. indek terakhir Batasan: Algoritma menggunakan operator pembandingan dua data untuk menguji relasi antar data (<, <=, >, atau >=)

Pengurutan Berbasis Seleksi (SelectionSort) ●

●

Ide: Pada setiap iterasi, cari data dengan nilai terbesar dan taruh di lokasi terakhir. Algoritma SelectionSort: (1)i = n (2)while i > 1 do (3) j = Max(A, 1, i) (4) TukarPosisi(A, i, j) (5) i = i – 1 (6)endwhile

Pengurutan Berbasis Seleksi ●

Dengan fungsi max sbb:

●

fungsi Max( A, awal, akhir ) returns imax (1)imax = awal (2)j = imax + 1 (3)while j <= akhir do (4)

if A[j] > A[imax] then imax = j

(5)

j=j+1

(6)endwhile (7)return imax

Contoh Proses Pengurutan

Beberapa Obvervasi ●

●

Pengurutan yang sama dapat diperoleh dengan mencari nilai terkecil dan ditaruh diawal array Stabil adalah istilah untuk pengurutan, dimana apabila ada data yang ekivalen (sama besar), setelah diurutkan, urutan semula tetap dipertahankan. –

Apakah Selection Sort stabil?

Pengurutan Berbasis Seleksi ●

Kebenaran algoritma tersebut dalam mengurutkan data bergantung pada bukti untuk dua hal berikut: –

Algoritma tersebut akan berhenti setelah mengurutkan data

–

Setelah berhenti, data memang terurut

Pengurutan Berbasis Seleksi ●

Algoritma tersebut pasti akan berhenti karena: –

Semua instruksi didalam loop tersebut finite, atau pasti akan selesai/berhenti

–

Iterasi bergantung pada variabel i, dan variabel i bergerak dari n s.d. 2 (sebelum i mencapai nilai 1 sudah keluar dari loop).

Loop Invarian Algoritma SelectionSort ●

●

●

Untuk membuktikan kebenaran algoritma pengurutan diatas, perhatikan baris 3 (while i > 1 do) Apabila algoritma tersebut benar, maka setiap memasuki loop tersebut, selalu berlaku kondisi (loop invarian) –

Data A[i+1..n] sudah terurut, dan

–

Data A[1..i] < data A[i+1..n]

Sehingga pada saat keluar dari loop tersebut, atau i = 1, maka –

A[2..n] sudah terurut, dan

–

A[1] lebih kecil dari semua yang lain

–

DPL, A[1..n] seluruhnya terurut

Pembuktian dengan induksi ●

Pada awal iterasi, i == n –

●

Basis: trivial karena belum ada data terurut

Hipotesis: asumsi kondisi berlaku pada 1 < i==k < n –

A[k+1..n] terurut

–

A[1..k] < A[k+1..n]

●

Induksi: Buktikan tetap berlaku untuk iterasi i==k-1

●

Proses didalam loop pada iterasi ke-i==k

●

–

j berisi data terbesar diantara A[1..k]

–

Karena TukarPosisi maka A[k,k+1, ..n] terurut dan A[1..i1] < A[k, k+1..n]

–

Pada langkah terakhir i=i-1, maka kondisi diatas kembali berlaku untuk i==k-1

Terbukti dengan induksi

Penggunaan Sumber Daya ●

●

Biasanya dihitung terkait dengan banyaknya data masukan Sumber daya dapat berupa waktu eksekusi,

●

Atau besar memori yang digunakan,

●

Atau kebutuhan jaringan, dll

Perhitungan Sumber Daya ●

●

Tidak menjumlahkan seluruh operasi yang dilakukan: –

Terlalu rumit

–

Waktu eksekusi setiap instruksi berbeda untuk jenis prosesor berlainan

–

Yang dicari adalah tren atau relasi antara kebutuhan sumber daya terhadap pertumbuhan data

Cukup menghitung operator yang relevan –

Pada proses pengurutan diatas, operator perbandingan data dianggap relevan

Fungsi Kompleksitas ●

●

Terhadap data masukan, adalah fungsi asimtot untuk perkiraan kebutuhan sumber daya: –

Apabila merupakan perkiraan maksimum, fungsi tersebut menjadi batas atas

–

Sebaliknya,jika perkiraan kebutuhan minimum, fungsi adalah batas bawah

Dapat merupakan perkiraan kompleksitas: –

Rata-rata atas suatu distribusi data tertentu

–

Atas situasi terburuk yang mungkin terjadi

Batas Atas dan Batas Bawah ●

Notasi O-Besar

●

Notasi Omega-Besar

●

Notasi Theta-Besar

●

Notasi o-kecil

●

Notasi omega-kecil

Analisis Kompleksitas Pengurutan berbasis Seleksi ●

●

Apabila fungsi Max memerlukan waktu Θ(i) pada iterasi ke-i, dimana i=2..n Maka waktu yang diperlukan adalah n

(n−1)(n+2) 2 )=Θ(n ) ∑ Θ(i)=Θ( 2 i=2

Latihan (1) Dengan induksi buktikan kebenaran fungsi Max (2) Tunjukan Θ(n) adalah kebutuhan waktu eksekusi Max (3) Mengapa hasil yang diperoleh dalam notasi-Θ? (4) Pelajari dan lakukan eksperimen dengan algoritma Selection sort, Bublesort, dan Insertion sort. Mengapa Bublesort lebih lambat daripada yang lain? (5)Apakah Bublesort dan Insertion sort stabil?

Pengurutan Yang Lebih Cepat ●

Alasan perlu solusi yang lebih cepat

●

Alasan saat solusi lebih cepat tidak diperlukan

●

●

Percepatan dapat diperoleh dengan menghilangkan redudansi proses Sumber redundansi proses: –

Pemeriksaan yang tidak perlu

–

Pengulangan pemeriksaan

–

Tidak ada mekanisme memanfaatkan hasil pemeriksaan sebelumnya

Pengurutan dengan Heap (HeapSort) ●

Heap: Struktur berbentuk pohon, dimana nilai data suatu node selalu lebih besar dari nilai data anak-anaknya –

●

●

Nilai data root selalu paling besar

Representasi heap dalam array: –

Anak node i adalah node 2*i dan 2*i+1

–

Root adalah node 1

Dua operasi heap: –

BangunHeap

–

PerbaikiHeap

Algoritma Heapsort ●

●

Ide: Memanfaatkan heap untuk mempercepat proses seleksi Algoritma: (1)BangunHeap(A, n) (2)i = n (3)while i > 1 do (4)

TukarPosisi(A, 1, i)

(5)

PerbaikiHeap(A, 1, i-1)

(6)

i=i–1

(7)endwhile

●

PerbaikiHeap(A, i, n) (1)lanjut = true (2)while lanjut do (3)

lanjut = false

(4)

p = i; l = 2*i; r = l+1

(5)

if l <= n and A[l] > A[p] then p = l

(6)

if r <= n and A[r] > A[p] then p= r

(7)

if i != p then

(8)

TukarPosisi(A, i, p)

(9)

lanjut = true

(10)

i=p

(11)

endif

(12)endwhile

●

Prosedur BangunHeap(A, n) (1)i = floor(n/2) (2)while i >= 1 do (3)

PerbaikiHeap(A, i, n)

(4)

i=i-1

(5)endwhile

Pengurutan dengan Heap ●

●

Bukti kebenaran algoritma Heapsort mirip dengan bukti untuk algoritma sebelumnya Asalkan prosedur BangunHeap dan PerbaikiHeap selalu menaruh data terbesar diposisi A[1]

Kebenaran PerbaikiHeap ●

●

●

Prosedur ini berasumsi bahwa heap sudah benar, kecuali pada posisi ke-i Baris 4-6 prosedur tersebut membandingkan node ke-i dengan kedua anaknya, dan diperoleh node p dengan data terbesar. Jika node i bukan yang terbesar, baris 7-11 memastikan sekarang kembali menjadi yang terbesar

●

Baris 10 i menjadi p, sehingga asumsi kembali benar

●

Proses berhenti jika –

node i tidak mempunyai anak node lagi

–

data node i lebih besar dari data anak nodenya

Kebenaran BangunHeap ●

●

●

●

Pada awalnya, data belum membentuk heap Tapi, A[⌈n/2⌉..n] tidak mempunyai anak, sehingga masing2 memenuhi definisi sebagai sub-heap yang benar Dimulai dari i == ⌈n/2⌉-1,dengan demikian pada setiap iterasi, hanya node i yang mungkin melanggar aturan heap, dan ini dapat diperbaiki oleh PerbaikiHeap Sehingga saat akhir iterasi, i mencapai 1, seluruh heap terbentuk

Pengurutan dengan Heap ●

Kompleksitas PerbaikiHeap bergantung pada jumlah iterasi 2-12: –

Berhenti jika i == p atau i > ⌊n/2⌋

–

Atau berlanjut dengan i == 2*i atau 2*i+1

●

Sehingga diperoleh O(log(n) – log(i))

●

Untuk i == 1 maka log(1) = 0, atau O(log(n))

Pengurutan dengan Heap ●

Kompleksitas BangunHeap adalah akumulasi dari PerbaikiHeap n ⌊ ⌋ 2

n ∑ Ο(log(n)−log (i))≤ 2 Ο(log(n)) i=1 ●

Kompleksitas BangunHeap adalah O(n log(n))

Algoritma Heapsort ●

Algoritma: (1)BangunHeap(A, n)

O(n log n)

(2)i = n

O(1)

(3)while i > 1 do

n-1 iterasi

(4)

TukarPosisi(A, 1, i)

O(1)

(5)

PerbaikiHeap(A, 1, i-1)

O(log n – log i)

(6)

i=i–1

O(1)

(7)endwhile

Kompleksitas Heapsort ●

Kompleksitas Heapsort n

Ο(n log (n))+∑ Ο(log(n)−log(i)) i=2

.≤Ο(n log(n))+(n−1)Ο(log(n)) .≤2Ο(n log (n)) ●

Atau O(n log n)

Latihan (1) Pelajari algoritma Quicksort dan Mergesort. Bandingkan dengan algoritma Heapsort! Dalam kasus seperti apa Heapsort lebih baik, dan dalam kasus apa Quicksort lebih baik? Begitu juga, bandingkan dengan Mergesort. (2) Apakah Heapsort stabil atau tidak stabil? Bagaimana dengan Quicksort dan Mergesort?

Batas Optimal Pengurutan ●

●

●

Perbaikan proses seleksi, meningkatkan performa dari O(n2) menjadi O(n log n) Apakah mungkin untuk mendapatkan solusi secara asimtot lebih cepat lagi? Atau solusi yang sudah diperoleh yang paling cepat? Dengan menganalisis masalah yang dihadapi, dapat diketahui jumlah minimum operasi yang diperlukan!

Batas Optimal Pengurutan ●

●

●

●

Proses pengurutan pada dasarnya adalah proses permutasi dari data yang diberikan Untuk n data, maka akan ada n! (n faktorial) kemungkinan permutasi data Salah satu permutasi akan memberikan susunan data yang terurut Berapa banyak minimum operasi perbandingan (dalam situasi terburuk) untuk melakukan permutasi dari satu urutan ke satu urutan lain?

Pohon Keputusan ●

●

●

Permutasi dari satu susunan data ke susunan lain diperoleh melalui serangkaian operasi perbandingan. Setiap operasi menghasilkan dua alur berbeda, akibat dari dari kondisi True/False Karena itu, dari susunan data semula, sejumlah rangkaian operasi perbandingan kesemua kemungkinan n! permutasi susunan data membentuk graf pohon. (Pohon keputusan)

Pohon Keputusan ●

●

●

Masing2 algoritma sorting dengan suatu input susunan data awal akan membentuk pohon keputusan sendiri yang khas. Karena ide algoritma tersebut, sangat mungkin beberapa operasi membandingkan dua data yang itu2 lagi lebih dari sekali dalam satu alur untuk mencapai permutasi akhir yang diinginkan. Minimum operasi yang dibutuhkan untuk algoritma tsb == maksimum tinggi pohon keputusannya

Pohon Keputusan untuk 3 data

Optimalitas Proses Pengurutan ●

●

●

●

●

Algoritma ideal akan mempunyai pohon keputusan yang sangat balance dan tidak ada duplikasi operasi perbandingan dalam tiap jalurnya. Sehingga tinggi pohon adalah ⌈log(n!)⌉ atau Ω(n log n) Artinya hanya dengan operasi pembandingan, proses pengurutan data secara asimtotik tidak dapat lebih cepat dari Ω(n log n) Dpl. diisimpulkan Heapsort adalah algoritma optimal, atau Θ(n log n) Mungkin saja algoritma lain mempunyai eksekusi lebih cepat/efisien, tetapi kompleksitasnya tidak lebih baik

Latihan ●

Lengkapi bukti pohon keputusan diatas sehingga diperoleh Ω(n log n)

Menembus Batas ●

●

●

●

●

Dalam beberapa situasi, algoritma optimal yang paling efisienpun, mungkin masih belum mencukupi Kaji ulang masalah yang dihadapi –

Data mempunyai keterbatasan tertentu

–

Mungkin malah data tidak perlu diurutkan

Mungkin pengurutan tidak perlu dengan operasi perbandingan data Tetapi untuk menjamin keterurutan, setiap elemen data harus terakses, sehingga Ω(n) adalah batas trivial yang tidak dapat dilanggar

Pengurutan dengan Pencacahan (CountingSort) ●

●

●

Apabila rentang data (k) dari terkecil s.d. terbesar, terbatas atau k = O(n) Untuk kemudahan pembahasan, data dianggap bilangan integer Jumlah kemunculan data dapat dihitung, dan lokasi setelah terurut dapat diantisipasi

Pengurutan dengan Pencacahan ●

Algoritma CountingSort (1)for i = terkecil to terbesar do (2) C[i] = 0 (3)for i = 1 to n do (4) C[A[i]]++ (5)for i = terkecil+1 to terbesar do (6) C[A[i]] = C[A[i]] + C[A[i-1]] (7)for i = n downto 1 do (8) B[C[A[i]]] = A[i] (9) C[A[i]]--

Pengurutan dengan Pencacahan

Pengurutan dengan Pencacahan ●

●

Kebenaran CountingSort: –

Untuk data i dari terkecil s.d. terbesar,

–

Setelah pencacahan, C[i] berisi jumlah kemunculan masing2 data i

–

Setelah akumulasi, C[i] berisi jumlah data <= i

–

Dpl, C[i] dapat menunjukkan indek terbesar dimana data i disimpan setelah terurut (jika data i ada di A)

–

Dengan memeriksa data di A satu persatu, data dapat disimpan sesuai posisi di C[i], ke array B

–

Isi C[i] disesuaikan setelah data disimpan di B

Karena C[i] menunjuk posisi terbesar, dengan memulai pemeriksaan A dari indek terbesar, hasil terurut akan stabil!

Kompleksitas CountingSort ●

Proses inisialisasi array pencacah C –

●

Proses pencacahan isi array A –

●

O(k)

Proses redistribusi data dari A ke B –

●

O(n)

Proses akumulasi hasil pencacahan di C –

●

O(k)

O(n)

Total adalah O(k+n), –

sehingga jika k = O(n),

–

maka Countingsort adalah O(n)

Observasi CountingSort ●

●

●

Counting Sort tergantung atas rentang data yang diurutkan Counting Sort hanya membutuhkan waktu linear Counting Sort bersifat stabil

Pengurutan Bertahap Berdasar Kolom Data (RadixSort) ● ●

●

●

Untuk data yang lebih besar

Apabila data dapat dipecah terhadap kolom/digit data Pengurutan dimulai dari digit yang lebih kecil (least significant digit) Kemudian diulang, sampai ke digit terakhir (most significant digit)

Pengurutan Bertahap Berdasar Kolom Data ●

●

Pengurutan per kolom dapat menggunakan Counting Sort Karena rentang digit per kolom dapat jauh lebih sedikit dari jumlah data

Pengurutan Bertahap Berdasar Kolom Data

Algoritma RadixSort ●

Kompleksitas algoritma adalah

l×Ο(n) ● ●

dimana l adalah jumlah kolom Apabila l adalah konstan, maka diperoleh O(n)

Latihan (1) Apa yang perlu dilakukan jika data untuk CountingSort ternyata bukan integer? (2)Apa yang terjadi jika pada RadixSort, pengurutan dimulai dari digit kanan lebih dulu? (3) Pelajari algoritma BucketSort. Mengapa waktu algoritma tersebut juga linear terhadap besar input?

Latihan (4) Mengapa Ω(n) adalah batas bawah proses sorting? (5) Mengapa Counting Sort stabil? Bagaimana dengan Radixsort dan Bucketsort?

Rangkuman ●

Cari solusi efisien

●

Cari solusi lebih baik jika dibutuhkan

●

●

Batas atas usaha mencari solusi yang lebih baik Alternatif solusi jika solusi optimum belum memadai

Rujukan ●

●

T. H. Cormen, C. E. Leiserson, R. L. Rivest, dan C. Stein, “Introduction to Algorithms”, edisi 3, 2009. S Dasgupta, C. H. Papadimitrou, dan U. V. Vazirani, “Algorithms”, 2006.