Kompleksitas Algoritma

Pada bagian sebelumnya kita telah mempelajari mengenai algoritma yang baik, serta bagaimana membuktikan sebuah algoritma akan memberikan hasil yang benar. Selain memberikan hasil yang benar, efisiensi dari waktu eksekusi ataupun penggunaan memori dari algoritma adalah hal yang penting bagi sebuah algoritma. Bagian ini akan membahas bagaimana mengukur efisiensi sebuah algoritma, sehingga kita dapat memilih algoritma yang baik atau memperbaiki algoritma yang ada.

Langsung saja, kita mulai dengan sebuah contoh algoritma untuk menghitung perpangkatan dua bilangan. Hasil akhir dari kode yang akan dikembangkan direpresentasikan oleh fungsi matematis berikut:

\[f(x, y) = x^y\]

Salah satu implementasi sederhana untuk fungsi matematis di atas adalah:

def pangkat(x, y):
    hasil = 1
    for i in range(0, y):
        hasil = x * hasil
    return hasil

Pada dasarnya yang kita lakukan pada kode di atas ialah mengkalikan x dengan dirinya sendiri sebanyak y kali, dan menyimpan hasil kali tersebut di dalam variabel hasil. Baris hasil = x * hasil melakukan perkalian x dengan dirinya sendiri, dan perulangan dilakukan untuk memastikan baris ini dijalankan sebanyak y kali.

Dengan asumsi bahwa algoritma perpangkatan yang kita tuliskan di atas sudah benar, pertanyaan selanjutnya tentunya adalah: seberapa efisien kah algoritma tersebut?

Terdapat banyak cara untuk mengukur efisiensi sebuah algoritma, tentunya dengan kelebihan dan kekurangan dari masing-masing cara tersebut. Mari kita lihat cara mengukur efisiensi yang paling sederhana terlebih dahulu: melihat berapa langkah yang perlu dijalankan untuk menyelesaikan algoritma tersebut. Jika kita memanggil fungsi pangkat seperti berikut:

pangkat(2, 1)

Maka kode akan dieksekusi seperti berikut:

hasil = 1
for i in range(0, 1):
    hasil = 2 * hasil
return hasil

yang kita perulangan for yang ada kita kembangkan akan menjadi:

hasil = 1
hasil = 2 * hasil
return hasil

Total terdapat tiga langkah yang perlu dijalankan untuk mendapatkan hasil pangkat yang diinginkan. Sangat sederhana dan mudah. Bagaimana jika kita naikkan nilai dari y sehingga kita memanggil pangkat(2, 2)?

Kode yang dieksekusi akan menjadi:

hasil = 1
for i in range(0, 2):
    hasil = 2 * hasil
return hasil

yang ketika diuraikan menjadi:

hasil = 1
hasil = 2 * hasil
hasil = 2 * hasil
return hasil

dengan total 4 langkah eksekusi. Perhatikan bagaimana akibat dari meningkatkan nilai y, jumlah eksekusi dari kode di dalam loop meningkat. Berdasarkan apa yang kita dapatkan sejauh ini, kita dapat menyimpulkan bahwa jika dilakukan pemanggilan pangkat(2, 5) maka kita akan mendapatkan hasil eksekusi:

hasil = 1
hasil = 2 * hasil
hasil = 2 * hasil
hasil = 2 * hasil
hasil = 2 * hasil
hasil = 2 * hasil
return hasil

dan seterusnya. Kesimpulan lain apa lagi yang bisa kita tarik dari hal ini? Ya, baris hasil = x * hasil dijalankan sebanyak y kali! Secara sederhana, tabel di bawah menampilkan berapa kali setiap baris yang ada dalam fungsi pangkat dieksekusi:

Baris Kode | Jumlah Eksekusi
hasil = 1 | 1
hasil = x * hasil | y
return hasil | 1

sehingga kita dapat mengatakan bahwa fungsi pangkat akan selalu diselesaikan dalam 2 + y langkah. Melihat bagiamana y akan mempengaruhi jumlah langkah eksekusi, mari kita lihat seberapa banyak pengaruh y terhadap jumlah langkah eksekusi kode:

Y Proses Perhitungan Jumlah Langkah
1 2 + 1 3
10 2 + 10 12
100 2 + 100 102
1000 2 + 1000 1002
10000 2 + 10000 10002

Dari tabel di atas kita dapat melihat bagiamana semakin meningkatnya jumlah dari y, semakin nilai 2 yang ditambahkan menjadi tidak relevan. Perbedaan jumlah langkah 1000000 dengan 1000002 tentunya tidak banyak! Dengan begitu, kita dapat menyederhanakan fungsi perhitungan jumlah langkah pangkat dengan mengatakan bahwa fungsi pangkat akan selalu diselesaikan dalam y langkah. Dengan kata lain, kecepatan atau efisiensi dari fungsi pangkat bergantung kepada y.

Semakin besar nilai y, maka jumlah langkah eksekusi akan semakin meningkat. Hal ini tentunya sangat berpengaruh terhadap efisiensi total dari sebuah algoritma. Bayangkan jika jumlah langkah yang diperlukan bukanlah y, melainkan \(y^2\):

Y Jumlah Langkah (\(y\)) Jumlah Langkah (\(y^2\))
1 1 1
10 10 100
100 100 10000
1000 1000 1000000
10000 10000 100000000

Perhatikan bagaimana pertumbuhan jumlah langkah terus menerus meningkat tajam, setiap kali kita menambahkan nilai y 10 kali lipat. Untuk memperjelas perbedaan pertumbuhan lagi, perhatikan gambar berikut:

Tingkat Pertumbuhan Fungsi Pangkat

Tingkat Pertumbuhan Fungsi Pangkat

Peningkatan jumlah langkah eksekusi seperti inilah yang menyebabkan kita mengukur efisiensi algoritma dengan ukuran pertumbuhan jumlah langkah eksekusi relatif terhadap jumlah data. Melihat grafik pertumbuhan yang diberikan, fungsi pangkat yang dikembangkan dapat dikatakan memiliki tingkat pertumbuhan yang linear.

Notasi Asimtotik

Perhitungan pertumbuhan fungsi seperti yang kita lakukan sebelumnya sangat krusial dalam menghitung efisiensi sebuah algoritma. Seperti layaknya hal-hal krusial lainnya pada ilmu komputer, tentunya fungsi pertumbuhan ini juga memiliki notasi matematika khusus. Penulisan fungsi pertumbuhan dilakukan dengan menggunakan notasi asmtotik.

Terdapat beberapa jenis notasi asimtotik, tetapi kita hanya akan menggunakan dan membahas satu notasi saja, yaitu notasi Big-O. Big-O dipilih karena merupakan notasi yang paling populer dan paling banyak digunakan pada kalangan peneliti ilmu komputer. Notasi Big-O digunakan untuk mengkategorikan algoritma ke dalam fungsi yang menggambarkan batas atas (upper limit) dari pertumbuhan sebuah fungsi ketika masukan dari fungsi tersebut bertambah banyak. Singkatnya, perhitungan jumlah langkah dan pertumbuhannya yang kita lakukan pada bagian sebelumnya merupakan langkah-langkah untuk mendapatkan fungsi Big-O dari sebuah algoritma.

Big-O, seperti namanya, dituliskan sebagai fungsi “O” dengan nilai masukan berupa tingkat pertumbuhan dari fungsi yang dijabarkan. Misalnya, algoritma perpangkatan dengan pertumbuhan linear yang kita kembangkan pada bagian sebelumnya memiliki kelas Big-O \(O(n)\).

Karena berguna untuk mengkategorikan algoritma, terdapat beberapa jenis kelas efisiensi umum yang dijumpai dalam Big-O, yaitu:

Fungsi Big-O Nama
\(O(1)\) Konstan
\(O(\log n)\) Logaritmik
\(O(n)\) Linear
\(O(n \log n)\) n log n
\(O(n^2)\) Kuadratik
\(O(n^m)\) Polinomiale
\(O(n!)\) Faktorial

Apa guna dan penjelasan dari masing-masing kelas kompleksitas yang ada? Mari kita lihat satu per satu.

Kriteria Efisiensi Umum

Bagian ini akan menjelaskan beberapa contoh kriteria kompleksitas algoritma yang umum dijumpai, beserta dengan contoh kode algoritma yang memiliki kompleksitas tersebut.

O(1): Kompleksitas Konstan

Sebuah algoritma yang memiliki kompleksitas konstan tidak bertumbuh berdasarkan ukuran dari data atau masukan yang diterima algoritma tersebut. Bahkan, algoritma dengan kompleksitas ini tidak akan bertumbuh sama sekali. Berapapun ukuran data atau masukan yang diterima, algoritma dengan kompleksitas konstan akan memiliki jumlah langkah yang sama untuk dieksekusi.

Karena sifatnya yang selalu memiliki jumlah langkah tetap, algoritma dengan kompleksitas merupakan algoritma paling efisien dari seluruh kriteria yang ada. Contoh dari algoritma yang memiliki kompleksitas konstan ialah algoritma yang digunakan untuk menambahkan elemen baru ke dalam linked list. Contoh implementasi algoritma ini pada bahasa C adalah sebagai berikut:

void add_list(node *anchor, node *new_list)
{
    new_list->next = anchor->next;
    anchor->next = new_list;
}

Seperti yang dapat dilihat pada kode di atas, algoritma untuk menambahkan elemen baru ke dalam linked list tidak memerlukan perulangan, percabangan, ataupun banyak langkah. Untuk menambahkan elemen baru, kita cukup menjalankan dua langkah saja, tidak peduli berapapun ukuran awal dari linked list yang ada. Dengan kata lain, berapapun ukuran linked list awal, langkah untuk untuk menambahkan elemen baru adalah konstan, yaitu dua langkah. Hal ini lah yang menyebabkan algoritma ini dikatakan memiliki kompleksitas konstan.

Tingkat pertumbuhan dari algoritma dengan kompleksitas konstan dapat dilihat pada gambar berikut:

Tingkat Pertumbunan Algoritma Kompleksitas Konstan

Tingkat Pertumbunan Algoritma Kompleksitas Konstan

O(log n): Kompleksitas Logaritmik

Algoritma dengan kompleksitas logaritmik merupakan algoritma yang menyelesaikan masalah dengan membagi-bagi masalah tersebut menjadi beberapa bagian, sehingga masalah dapat diselesaikan tanpa harus melakukan komputasi atau pengecekan terhadap seluruh masukan. Contoh algoritma yang ada dalam kelas ini adalah algoritma binary search. Mari kita hitung nilai kompleksitas dari binary search!

Berikut adalah implementasi dari binary search dengan bahasa python:

def binary_search(lst, search):
    lower_bound = 0
    upper_bound = len(lst) - 1

    while True:
        if upper_bound < lower_bound:
            print("Not found.")
            return -1

        i = (lower_bound + upper_bound) // 2

        if lst[i] < search:
            lower_bound = i + 1
        elif lst[i] > search:
            upper_bound = i - 1
        else:
            print("Element " + str(search) + " in " + str(i))
            return 0

Mari kita hitung jumlah langkah yang diperlukan untuk mendapatkan kelas kompleksitas dari binary search. Berikut adalah tahapan perhitungan untuk mendapatkan jumlah langkah yang diperlukan:

  1. Langkah yang akan selalu dieksekusi pada awal fungsi, yaitu inisialisasi lower_bound dan upper_bound: 2 langkah.
  2. Pengecekan kondisi while (pengecekan tetap dilakukan, walaupun tidak ada perbandingan yang dijalankan): 1 langkah.
  3. Pengecekan awal (if upper_bound < lower_bound): 1 langkah.
  4. Inialisasi i: 1 langkah.
  5. Pengecekan kondisi kedua (if lst[i] < search: ...), kasus terburuk (masuk pada else dan menjalankan kode di dalamnya): 4 langkah.

Dan setelah melalui langkah kelima, jika elemen belum ditemukan maka kita akan kembali ke langkah kedua. Perhatikan bahwa sejauh ini, meskipun elemen belum ditemukan atau dianggap tidak ditemukan, kita minimal harus menjalankan 2 langkah dan pada setiap perulangan while kita menjalankan 7 langkah. Sampai di titik ini, model matematika untuk fungsi Big-O yang kita dapatkan ialah seperti berikut:

\[f(n) = 2 + 7(\text{jumlah perulangan})\]

Pertanyaan berikutnya, tentunya adalah berapa kali kita harus melakukan perulangan? Berhentinya kondisi perulangan ditentukan oleh dua hal, yaitu:

  1. Kondisi upper_bound < lower_bound, dan
  2. Pengujian apakah lst[i] == search, yang diimplikasikan oleh perintah else.

Perhatikan juga bagaimana baik nilai upper_bound maupun lower_bound dipengaruhi secara langsung oleh i, sehingga dapat dikatakan bahwa kunci dari berhentinya perulangan ada pada i. Melalui baris kode ini:

i = (lower_bound + upper_bound) // 2

Kita melihat bahwa pada setiap iterasinya nilai i dibagi 2, sehingga untuk setiap iterasinya kita memotong jumlah data yang akan diproses (\(n\)) sebanyak setengahnya. Sejauh ini kita memiliki model matematika seperti berikut (konstanta \(2\) dihilangkan karena tidak berpengaruh):

\[f(n) = 7f(\frac{n}{2})\]

yang jika diturunkan lebih lanjut akan menjadi:

\[\begin{split}f(n) & = 7f(\frac{n}{2}) \\ & = 7 * (7f(\frac{n}{4})) \\ & = 49f(\frac{n}{4}) \\ & = 49 * (7f(\frac{n}{8})) \\ & ... \\ & = 7^k f(\frac{n}{2^k})\end{split}\]

di mana kita ketahui kondisi dari pemberhentian perulangan adalah ketika sisa elemen list adalah 1, dengan kata lain:

\[\begin{split}\frac{n}{2^k} & = 1 \\ n & = 2^k \\ \log_2 n & = k\end{split}\]

Sehingga dapat dikatakan bahwa binary search memiliki kompleksitas \(O(\log_2n)\), atau sederhananya, \(O(\log n)\).

Tingkat pertumbuhan algoritma dengan kompleksitas logaritmik dapat dilihat pada gambar berikut:

Tingkat Pertumbunan Algoritma Kompleksitas Logaritmik

Tingkat Pertumbunan Algoritma Kompleksitas Logaritmik

O(n): Kompleksitas Linear

Algoritma dengan kompleksitas linear bertumbuh selaras dengan pertumbuhan ukuran data. Jika algoritma ini memerlukan 10 langkah untuk menyelesaikan kalkulasi data berukuran 10, maka ia akan memerlukan 100 langkah untuk data berukuran 100. Contoh dari algoritma dengan kompleksitas linear telah diberikan pada bagian sebelumnya, yaitu perhitungan pangkat bilangan. Contoh lain dari algoritma dengan kompleksitas linear adalah linear search.

Linear search melakukan pencarian dengan menelusuri elemen-elemen dalam list satu demi satu, mulai dari indeks paling rendah sampai indeks terakhir. Berikut adalah implementasi dari linear search pada python:

def linear_search(lst, search):
   for i in range(0, len(lst)):
       if lst[i] == search:
           print("Nilai ditemukan pada posisi " + str(i))
           return 0
   print("Nilai tidak ditemukan.")
   return -1

Dengan menggunakan cara perhitungan yang sama pada perhitungan pangkat, kita bisa mendapatkan jumlah eksekusi kode seperti berikut (dengan asumsi n = len(lst)):

Kode Jumlah Eksekusi
for i in range(0, len(lst)) \(1\)
if lst[i] == search \(n\)
print("Nilai ditemukan... \(1\)
return 0 \(1\)
print("Nilai tidak ... \(1\)
return -1 \(1\)

Sehingga nilai kompleksitas dari linear search adalah \(5 + n\), atau dapat dituliskan sebagai \(O(n)\). Adapun grafik pertumbuhan untuk kompleksitas \(O(n)\) adalah seperti berikut:

Tingkat Pertumbunan Algoritma Kompleksitas Linear

Tingkat Pertumbunan Algoritma Kompleksitas Linear

O(n log n)

Algoritma dengan kompleksitas \(n \log n\) memiliki cara perhitungan yang sangat mirip dengan algoritma \(\log n\). Pada dasarnya algoritma kelas ini merupakan algoritma \(\log n\) yang dijalankan sebenyak \(n\) kali. Contoh sederhananya, misalkan kita diminta untuk mencari sepasang bilangan di dalam sebuah list yang jika ditambahkan akan bernilai 0. Asumsikan list yang diberikan sudah terurut.

Salah satu solusi yang paling sederhana ialah dengan menelusuri seluruh list, satu demi satu (kompleksitas: \(n\)) lalu mencari elemen yang bernilai invers dari elemen sekarang menggunakan binary search (kompleksitas: \(\log n\)). Mari kita lihat contoh implementasi dari fungsi ini terlebih dahulu:

def zero_sum(lst):
    n = len(lst)
    for i in range(0, n):
        j = binary_search(lst, -1 * lst[i])
        if j > i:
            n1 = str(lst[i])
            n2 = str(lst[j])
            print("Zero sum: " + n1 + " and " + n2 + "\n")

Perhatikan bagaimana kita melakukan binary search sebanyak \(n\) kali, sehingga secara sederhana kompleksitas yang akan kita dapatkan adalah \(n * \log n = n \log n\). Adapun grafik pertumbuhan untuk kompleksitas \(O(n \log n)\) adalah seperti berikut:

Tingkat Pertumbunan Algoritma Kompleksitas n log n

Tingkat Pertumbunan Algoritma Kompleksitas n log n

O(\(n^m\)): Kompleksitas Polinomial

Algoritma dengan kompleksitas polinomial merupakan salah satu kelas algoritma yang tidak efisien, karena memerlukan jumlah langkah penyelesaian yang jauh lebih besar daripada jumlah data. Untuk lebih jelasnya, mari kita lihat salah satu contoh algoritma yang memiliki kompleksitas polinomial:

def kali(a, b):
    res = 0
    for i in range(a):
        for j in range(b):
            res += 1
    return res

Algoritma di atas melakukan perkalian antara \(a\) dan \(b\), dengan melakukan penambahan \(1\) sebanyak \(b\) kali, yang hasilnya ditambahkan sebanyak \(a\) kali. Mengabaikan dua langkah, yaitu awal (res = 0) dan akhir (return res) kode, kita dapat melihat total langkah yang diperlukan oleh perulangan bersarang yang ada seperti berikut:

Kode Jumlah Langkah
for i in range(b): \(a\)
res += 1 \(b\)

dan karena pada setiap iterasi kita harus menjalankan kode for i in range(b), maka dapat dikatakan kompleksitas dari kode di atas adalah:

\[a * b\]

yang ketika nilai \(a\) dan \(b\) sama akan menjadi:

\[a^2\]

atau dapat ditulis sebagai \(n^2\) yang diabstrakkan sebagai \(n^m, m = 2\). Grafik pertumbuhan untuk kompleksitas polinomial adalah sebagai berikut:

Tingkat Pertumbunan Algoritma Kompleksitas Eksponensial

Tingkat Pertumbunan Algoritma Kompleksitas Eksponensial

Perbandingan Pertumbuhan Seluruh Kompleksitas

Setelah melihat seluruh nilai kompleksitas yang ada, tentunya kita dapat melihat kelas algoritma yang paling efisien dan paling tidak efisien. Gambar berikut memperlihatkan perbandingan tingkat pertumbuhan antara masing-masing kompleksitas yang telah dipelajari:

Perbandingan Tingkat Pertumbuhan Tiap Kompleksitas

Perbandingan Tingkat Pertumbuhan Tiap Kompleksitas

Pengembangan algoritma idealnya diusahakan mendapatkan kompleksitas \(O(1)\) atau \(O(\log n)\). Sayangnya pada kenyataannya kita tidak akan selalu mendapatkan kompleksitas terbaik dalam merancang algoritma. Jika tidak dapat mencapai kompleksitas maksimal, hal terbaik yang dapat kita lakukan ketika mengembangkan solusi dari masalah adalah melihat apakah masalah yang ada dapat diselesaikan dengan algoritma yang ada terlebih dahulu, sebelum mengembangkan algoritma baru. Hal ini memastikan kita mendapatkan kompleksitas yang paling efisien sampai saat pengembangan solusi.

Kesimpulan

Pada bagian ini kita telah mempelajari bagaimana melakukan analisa efisiensi algoritma dengan menggunakan notasi Big-O. Kita juga melihat bagaimana algoritma yang paling efisien memiliki kompleksitas \(O(1)\), dengan kompleksitas \(O(n!)\) sebagai kelas kompleksitas yang paling tidak efisien. Dengan mengerti efisiensi algoritma, diharapkan pembaca dapat memilih dan merancang algoritma yang sesuai dengan kebutuhan untuk menyelesaikan masalah.

Pada bagian selanjutnya kita akan mulai mengembangkan algoritma dengan menggunakan konsep pemrograman.

Bagikan Tulisan
comments powered by Disqus
Kembali ke bertzzie.com