.png)
1. Pengertian
Kompleksitas Algoritma
Dalam matematika
dan komputasi algoritma atau algoritme merupakan kumpulan perintah untuk
menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara
bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan
catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi
sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua
kondisi awal yang memenuhi kriteria, dalam hal ini berbeda dengan heuristik Algoritma
sering mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika boolean dan perbandingan) sampai
tugasnya selesai.
Desain dan analisis algoritma adalah
suatu cabang khusus dalam ilmu komputer yang mempelajari karakteristik dan
performa dari suatu algoritma dalam menyelesaikan masalah, terlepas dari
implementasi algoritma tersebut. Dalam cabang disiplin ini algoritma dipelajari
secara abstrak, terlepas dari sistem komputer atau bahasa pemrograman yang
digunakan. Algoritma yang berbeda dapat diterapkan pada suatu masalah dengan
kriteria yang sama.
Kompleksitas dari suatu
algoritma merupakan ukuran seberapa banyak komputasi yang dibutuhkan algoritma
tersebut untuk menyelesaikan masalah. Secara informal, algoritma yang dapat
menyelesaikan suatu permasalahan dalam waktu yang singkat memiliki kompleksitas
yang rendah, sementara algoritma yang membutuhkan waktu lama untuk
menyelesaikan masalahnya mempunyai kompleksitas yang tinggi.
2. Sejarah Istilah Algoritma
Kata
algoritma berasal dari latinisasi nama seorang ahli matematika dari Uzbekistan Al Khawārizmi
(hidup sekitar abad ke-9), sebagaimana tercantum pada terjemahan karyanya dalam
bahasa latin dari abad ke-12 "Algorithmi de numero Indorum". Pada
awalnya kata algorisma adalah istilah yang merujuk kepada aturan-aturan
aritmetis untuk menyelesaikan persoalan dengan menggunakan bilangan numerik
arab (sebenarnya dari India, seperti tertulis pada judul di atas).
Pada abad
ke-18, istilah ini berkembang menjadi algoritma yang mencakup semua prosedur atau urutan langkah
yang jelas dan diperlukan untuk menyelesaikan suatu permasalahan. Masalah
timbul pada saat akan menuangkan bagaimana proses yang harus dilalui dalam
suatu/sebuah sistem (program) bagi komputer sehingga pada saat eksekusinya,
komputer dapat bekerja seperti yang diharapkan. Programer komputer akan lebih
nyaman menuangkan prosedur komputasinya atau urutan langkah proses dengan
terlebih dahulu membuat gambaran (diagram alur) diatas kertas.
3. Notasi
Algoritma yang Efisien
Perhatikan
contoh berikut: Anda diberikan N
buah titik di koordinat dua dimensi. Tugas anda adalah mencari pasangan titik
yang memiliki jarak terdekat.
Terdapat (N2)
kemungkinan pasangan titik. Jika anda melakukan pemeriksaan satu per satu
terhadap semua kemungkinan, maka anda akan memeriksa sebanyak N×(N−1) kali.
Dengan kata lain akan ada N2−N
komputasi yang dilakukan. Kita dapat menyatakan algoritma memeriksa semua kemungkinan
ini memiliki kompleksitas O(N2−N) .
Mengapa? Karena banyaknya komputasi yang diperlukan proporsional N2−N terhadap
besarnya masukan ( N ).
Sekarang
anda diberikan N
buah kunci dan M
buah pintu yang terkunci. Sebuah kunci bisa saja cocok dengan lebih dari satu
lubang kunci pintu. Tugas anda adalah menentukan pasangan kunci dan pintu yang
sesuai.
Jika anda
memeriksa setiap kunci dengan setiap pintu, artinya akan ada N×M percobaan.
Dengan begitu kita bisa katakan kompleksitas algoritma coba semua kemungkinan
ini O(NM) ,
karena banyaknya komputasi proporsional NM terhadap banyaknya kunci dan pintu ( dan ).
Notasi
seperti O(N2−N)
dan O(NM)
disebut sebagai notasi Big-O. Arti sebenarnya dari notasi ini adalah perkiraan
komputasi yang diperlukan algoritma berdasarkan nilai variabel yang
mempengaruhinya (dalam kasus O(N2−N)
adalah N ,
sementara dalam O(NM)
adalah N
dan M ).
4. Kompleksitas
Algoritma Secara Umum
Secara
umum, dapat dikatakan ada beberapa jenis kompleksitas: konstan, logaritmik,
polinomial, dan eksponensial. Berikut ulasannya:
1. Konstan, O(1) Komputasi algoritma tidak bergantung pada masukan. Contohnya adalah diberikan fungsi kuadrat ax2+bx+c , tugas anda adalah menentukan lokasi di mana nilai fungsinya akan menjadi titik ekstrim. Anda cukup gunakan rumus −b2a untuk ini. Dalam competitive programming, algoritma dengan kompleksitas O(1) tidak mungkin mendapatkan TLE karena sudah paling cepat (jika TLE, anda patut curiga ada suatu kesalahan).
2. Logaritmik, O(logN) Kompleksitas
yang sangat baik karena pertumbuhannya lambat. Contoh algoritma dengan
kompleksitas ini dalah binary search. Sesuai dengan aturan bahwa konstanta
tidak ditulis dalam notasi Big-O, log2N , log3N , atau log102N cukup
ditulis dengan logN
saja. Karena logcN=logNlogc .
3. Polinomial, O(N) , O(N2) , O(Nc) ,
terkadang juga O(NlogN)
termasuk di dalamnya
Nilai baik atau tidaknya kompleksitas polinomial bergantung pada derajat
terbesarnya.
4. Eksponensial, O(N!) , O(cN) , O(NN)Biasanya
dihindari dalam competitive programming, kecuali jika banyaknya masukan cukup
kecil atau time limit yang diberikan cukup banyak. Kompleksitas eksponensial
tumbuh sangat cepat.
Berikut ini adalah grafik yang
menyatakan pertumbuhan waktu eksekusi algoritma (T) terhadap N.
5.
6.
Kompleksitas dalam Competitive
Programming
Apa artinya jika program anda mempunyai kompleksitas O(N) atau O(N2) ? Jika anda mempunyai sekitar 2.000 data dan kompleksitas program anda O(N2) , maka secara kasar dibutuhkan 4.000.000 proses untuk memproses data-data tersebut.
Banyaknya
proses yang dilakukan dapat digunakan untuk mengira secara kasar apakah program
yang dibuat cukup cepat untuk diterima (lama waktu pengerjaan di bawah batas
waktu yang ditentukan). Para coder TOKI dan (mungkin) coder yang berpengalaman
lain dalam dunia competitive programming
mempunyai patokan bahwa mesin komputer dalam 1 detiknya dapat melakukan 100
juta proses. Sehingga untuk 4 juta proses di atas, secara kasar algoritma
tersebut membutuhkan waktu 4/100 detik untuk N
terbesar.
Dikatakan
secara kasar karena kita tidak bisa menentukan secara pasti berapa lama program
akan berjalan dengan jumlah data tertentu. Perlu ditekankan lagi bahwa patokan
100 juta proses/detik ini berdasarkan kemampuan mesin komputer pada sekitar
tahun 2000, sehingga untuk jaman sekarang bisa saja jauh lebih banyak proses
yang dapat dilakukan komputer dalam 1 detiknya. Untuk itulah sesi latihan/
practice pada setiap kontes pemrograman sangat penting, agar anda bisa mengetes
kemampuan mesin komputer yang digunakan sebagai grader.
Mungkin
anda bertanya, jika memang kemampuan mesin jaman sekarang bisa melakukan lebih
dari 100 juta proses/ detik, mengapa kita masih memakai patokan tersebut? Dalam
kebanyakan kasus, seringkali patokan 100 juta proses/ detik sudah lebih dari
cukup untuk menentukan apakah program anda cukup cepat atau tidak.
Setelah
anda membaca soal, anda perlu memikirkan bagaimana algoritma untuk memecahkan
persoalan tersebut. Anda perlu menghitung berapa kompleksitas algoritma yang
akan anda gunakan sebagai solusi. Jika dengan input maksimal, kompleksitas, dan
aturan 100 juta per detik algoritma anda dapat diterima, maka yang perlu
dilakukan berikutnya adalah coding.
Menghitung
kompleksitas algoritma pada umumnya tidak sulit. Sebagai contoh, jika anda
memerlukan proses mencoba semua kemungkinan pasangan dari N
buah benda, di mana pemeriksaan setiap pasangan dilakukan secara konstan, maka
kompleksitasnya adalah O(N2) .
Jika anda mengalikan matriks berukuran P×Q dan Q×R ,
maka kompleksitasnya adalah O(PQR)
karena ada P×R
sel yang harus diisi dimana setiap sel diisi dengan O(Q) .
Sebagai latihan, coba hitung berapa kompleksitas
dari persoalan dan algoritma berikut:
1
Menghitung rata-rata dari N
buah data dengan menjumlah setiap datanya, lalu dibagi dengan N .
2
Memeriksa apakah suatu string S palindrom dengan
cara membandingkan elemen pertama dengan terakhir, elemen kedua pertama dengan
kedua terakhir, dan seterusnya.
3
Menuliskan semua kemungkinan triplet (a, b, c),
dimana 1 ≤ a ≤ b ≤ c ≤ N .
4
Selama N > 0,
lakukan N=⌊N5⌋ . (fungsi pembulatan ke bawah)
5
Inisialisasi i =
1. Selama i×i
< N ,
tambahkan i dengan 1.
6
Menuliskan seluruh anggota dari tiap himpunan yang
termasuk sebagai anggota himpunan kuasa {1, 2, ..., N}. Sebagai catatan,
himpunan kuasa dari {1, 2} adalah {{}, {1}, {2}, {1, 2}}.
7
Mengalikan dua buah bilangan, a dan b, dengan
operator *.
Jawab: O(N) , O(|S|) (panjang string S), O(N3) , O(logN) , O(N−−√) , O(2N) , O(1) .
Beberapa competitive
programmer menganut general rules of
thumb berikut:
Kompleksitas
|
Keterangan
|
O(1), O(logN)
|
Aman, hampir selalu bekerja di bawah time limit
|
O(N−−√)
|
N≤1014
|
O(N)
|
N≤5000000
|
O(NlogN)
|
N≤500000
|
O(N2)
|
N≤2500
|
O(N3)
|
N≤200
|
O(N4)
|
N≤60
|
O(2N)
|
N≤20
|
O(N!)
|
N≤9
|
Jadi jika anda menemukan soal dengan batasan N
hingga 100.000, sudah pasti algoritma O(N2) TLE.
Refrence
:
No comments:
Post a Comment