Home >Documents >2. Algoritma, Kompleksitas dan Teori Bilang . Algoritma, Kompleksitas dan Teori Bilangan 2.1...

2. Algoritma, Kompleksitas dan Teori Bilang . Algoritma, Kompleksitas dan Teori Bilangan 2.1...

Date post:18-Apr-2018
Category:
View:231 times
Download:7 times
Share this document with a friend
Transcript:
  • 2. Algoritma, Kompleksitas dan Teori Bilangan

    2.1 Algoritma dan Fungsi Kompleksitas

    Algoritma adalah sekumpulan berhingga dari instruksi-instruksi untuk melakukan

    perhitungan/ komputasi atau memecahkan suatu masalah. Suatu algoritma yang baik harus

    memiliki sifat-sifat berikut ini:

    Masukan (input) dari himpunan tertentu

    Keluaran (output) pada himpunan tertentu (solusi)

    Definiteness dari setiap langkah perhitungan

    Kebenaran (correctness) dari keluaran untuk setiap masukan yang mungkin

    Keberhinggaan (finiteness) dari banyaknya langkah perhitungan

    Kefektifan (effectiveness) dari setiap langkah perhitungan dan

    Keterumuman (generality) dalam suatu kelompok permasalahan yang dipecahkan

    Kita akan memakai pseudocode untuk menuliskan algoritma, yang mirip dengan bahasa

    Pascal. Sebagai contoh pertama, tinjau algoritma mencari nilai maksimum dari suatu barisan

    yang panjangnya berhingga berikut ini.

    procedure max(a1, a2, , an: integers)

    max := a1

    for i := 2 to n

    if max < ai then max := ai

    {max adalah elemen terbesar dalam barisan}

    Dari masukan barisan a1, a2, ..., pertama-tama variabel max di-inisiasi dengan suku pertama

    barisan. Selanjutnya suku-suku berikutnya diambil dan dibandingkan dengan max, jika lebih

    besar maka nila lama max diganti dengan nilai baruyaitu suku sekarang, sedangkan jika

    (sama atau lebih kecil), algoritma mengambil suku berikutnyademikian seterusnya. Diakhir

    proses, suku terbesar dari barisan akan tertampung di dalam max.

    2. Algoritma, Kompleksitas dan Teori Bilangan - 1

  • Contoh kedua adalah algoritma pencarian linier (linear search), yaitu algoritma yang mencari

    elemen tertentu dari barisan berhingga secara linier.

    procedure linear_search(x: integer; a1, a2, , an:

    integers)

    i := 1

    while (i n and x ai)

    i := i + 1

    if i n then location := i

    else location := 0

    {letak dari elemen yang dicari adalah subscript dari suku

    yang sama dengan x, atau nol jika tidak ditemukan.}

    Pada algoritma pencarian linier, pertama-tama pencacah indeks i di-inisiasi ke harga 1.

    Selanjutnya suku barisan diambil satu persatu secara ber-urutan dan dibandingkan dengan

    bilangan yang dicari, yaitu x. Jika ditemukan, maka variable location di-assign dengan

    indeks dari suku tersebut, sedangkan jika tidak ditemukan, maka variable tersebut diberi

    harga nol. Eksekusi berakhir setelah ujung barisan dicapai, dengan variable location

    berisi indeks suku barisan yang dicari atau berisi nol jika tidak ditemukan. Pencarian yang

    demikian tentu saja akan memakan waktu yang sebanding dengan panjangnya barisan

    sehingga tidak efisien atau disebut bahwa kompleksitas algoritma ini besar.

    Gb. 2.1 Ilustrai algoritma pencarian biner

    a c d f g h j l m o p r s u v x z

    pusat pertamapusat kedua

    Interval-1Interval-2

    Interval-3

    pusat ketiga, KETEMU!

    2. Algoritma, Kompleksitas dan Teori Bilangan - 2

  • Kompleksitas bisa diturunkan jika dipakai teknik pencarian biner (binary search), akan tetapi

    masukannya harus terlebih dahulu diurutkan (ordered). Dalam pencarian biner, algoritma

    secara iteratif membatasi interval pencarian yang relevan hingga mendekati posisi suku

    barisan yang dicari. Berikut ini ilustrasi pencarian biner untuk huruf j

    Algoritma dalam bentuk pseudocode dari pencarian biner adalah sebagai berikut.

    procedure binary_search(x: integer; a1, a2, , an:

    integers)

    i := 1 {i is left endpoint of search interval}

    j := n {j is right endpoint of search interval}

    while (i < j)

    begin

    m := (i + j)/2

    if x > am then i := m + 1

    else j := m

    end

    if x = ai then location := i

    else location := 0

    {letak dari elemen yang dicari adalah subscript dari suku

    yang sama dengan x, atau nol jika tidak ditemukan.}

    Jelas bahwa dalam barisan yang terurut, pencarian biner lebih efisien daripada pencarian

    liniar. Selanjutnya muncul pertanyaan bagaimana cara menganalisa efisiensi dari suatu

    algoritma? Kita dapat mengukur efisiensi ini dengan

    Waktu (time): yakni banyaknya komputasi elementer dalam algoritma

    Ruang (space): adalah banyaknya sel memori yang dibutuhkan oleh algoritma.

    Ukuran ini secara berturut-turut disebut sebagai kompleksitas komputasi (computational

    complexity) dan kompleklsitas ruang (space complexity).

    Berapakah kompleksitas waktu dari algoritma pencarian linier ? Kita akan menentukan

    banyaknya proses perbandingan pada kasus terburuk (worst-case) sebagai fungsi dari panjang

    barisan n. Kasus terburuk dari algoritma pencarian linier muncul ketika elemen yang dicari

    2. Algoritma, Kompleksitas dan Teori Bilangan - 3

  • ternyata tidak ada didalam barisan masukan. Pada kasus tersebut, setiap suku dalam barisan

    akan dibandingkan dengan elemen yang dicari. Sehingga, untuk n buah elemen, loop

    while (i n and x ai)

    i := i + 1

    dilaksanakan n kali, sehingga memerlukan 2n buah proses perbandingan. Saat memasuki loop

    ke (n+1) kalinya, yang dieksekusi hanyalah perbandingan i n dan loop diakhiri.

    Akhirnya perbandingan

    if i n then location := i

    dieksekusi, sehingga pada kasus terburuk kompleksitas waktu adalah 2n + 2. Ini adalah nilai

    kompleksitas dari algoritma pencarian linier. Selanjutnya, berapakah kompleksitas waktu dari

    algoritma pencarian biner?

    Sekali lagi kita akan menentukan jumlah perbandingan pada kondisi terburuk sebagai fungsi

    dari banyaknya suku dalam deretan n. Kita asumsikan terdapat n=2k buah elemen di dalam

    barisan yang berarti bahwa k = log(n). Jika n bukan pangkat 2 dari suatu bilangan, barisan

    tersebut dapat dianggap sebagai bagian dari barisan lain yang lebih besar, dimana

    2k

  • elemen tersisa dalam interval pencarian. Pada kondisi ini, sejumlah 2k perbandingan telah

    dilakukan.

    Kemudian, dilakukan perbandingan: while (i < j). Setelah itu keluar dari loop dan

    perbandingan akhir adalah

    if x = ai then location := i

    Menentukan apakah elemen yang dicari sudah ketemu. Dengan demikian, total dari

    kompleksitas waktu untuk algoritma pencarian biner adalah 2k + 2 = 2 log(n) + 2. (NB: kita

    selalu mengasumsikan logaritma basis dua).

    Pada umumnya, untuk input yang kecil, kita tidak tertarik pada kompleksitas ruang maupun

    waktu. Perbedaan kompleksitas waktu untuk pencarian linier dengan pencarian biner tidak

    begitu berarti untuk n=10, tetapi sangat signifikan untuk n = 230. Misalkan, ada dua buah

    algoritma, sebut sebagai algoritma A dan algoritma B yang dapat memecahkan suatu kelas

    permasalahan. Kompleksitas waktu dari algoritma A adalah 5000n sedangkan kompleksitas

    dari algoritm B adalah 1.1n untuk masukan n buah elemen (barisan). Sekarang kita

    perhatikan perbandingan kompleksitas waktu dari algoritma A dan B sebagai berikut:

    Besarnya masukan Kompleksitas algoritma-A Kompleksitas algoritma-B

    n 5000n 1.1n

    10 50.000 3

    100 500.000 13.781

    1.000 5.000.000 2.51041

    1000.000 5109 4,81041392

    Ini berarti bahwa algoritma B tidak dapat dipakai untuk masukan dengan elemen yang besar,

    sedangkan dengan algoritma A, hal ini masih bisa diatasi. Jadi, yang paling penting dalam

    menghitung kompleksitas suatu algoritma adalah pertumbuhan dari fungsi kompleksitas.

    Pertumbuhan dari kompleksitas dengan meningkatnya besarnya masukan, n, adalah ukuran

    yang sesuai untuk membandingkan algoritma. Pertumbuhan fungsi kompleksitas

    dilambangkan dengan notasi O (dibaca big-O). Perhatikan definisi berikut ini.

    2. Algoritma, Kompleksitas dan Teori Bilangan - 5

  • Definisi: Misalkan f dan g adalah dua buah fungsi dari bilangan bulat ke bilangan riil. Kita

    katakan bahwa f(x) adalah O(g(x)) jika ada suatu konstanta C dan k sedemikian hingga

    |f(x)| C|g(x)|, saat x > k.

    Saat menganalisa perumbuhan dari fungsi kompleksitas, f(x) dan g(x) selalu positif. Oleh

    karena itu, kita dapat menyederhanakan persyaratan big-O menjadi

    f(x) Cg(x) saat x > k.

    Jika kita ingin menunjukkan bahwa f(x) adalah O(g(x)), kita hanya perlu menentukan satu

    buah pasangan (C, k) (yang tidak pernah unik).

    Ide dibelakang notasi big-O adalah penentuan batas atas (upper boundary) dari perumbuhan

    suatu fungsi f(x) untuk x besar. Batas ini diberikan oleh fungsi g(x) yang biasanya jauh lebih

    sederhana daripada f(x). Kita menerima konstanta C dalam persyaratan

    f(x) Cg(x) saat x > k.

    karena C tidak pernah tumbuh sejalan dengan tumbuhnya x. Kita hanya tertarik pada x besar,

    sehingga jika f(x) > Cg(x) untuk x k, bukanlah suatu masalah. Perhatikan contoh soal

    berikut.

    Soal: Tunjukkan bahwa f(x) = x2 + 2x + 1 adalah O(x2).

    Jawab: Untuk x > 1: x2 + 2x + 1 x2 + 2x2 + x2

    x2 + 2x + 1 4 x2

    Karena itu, untuk C = 4 dan k = 1: f(x) C x2 ketika x > k.

    f(x) adalah O(x2).

    Selanjutnya mungkin timbul pertanyaan: jika f(x) adalah O(x2), apakah f(x) juga O(x3)?.

    Jawabnya adalah ya, karena x3 tumbuh lebih cepat daripada x2, sehingga x3 juga tumbuh

    lebih cepat dibandingkan dengan f(x). Karena itu, kita selalu harus menemukan fungsi

    sederhana terkecil g(x) dimana f(x) adalah O(g(x)).

    2. Algoritma, Kom

Embed Size (px)
Recommended