Asymptotic Analysis

1. Pengenalan

Asymptotic Analysis adalah teknik untuk mempelajari kinerja algoritma saat ukuran inputnya mendekati tak terbatas, dengan fokus pada waktu eksekusi. Ini digunakan untuk menganalisis kinerja algoritma dan untuk menentukan efisiensi dan skalabilitasnya. Asymptotic Analysis membantu dalam memahami perilaku algoritma ketika ukuran input tumbuh lebih besar dan memberikan wawasan tentang kompleksitas waktu dan ruang algoritma. Informasi ini sangat penting dalam merancang algoritma yang efisien untuk pemrosesan dan analisis data skala besar, yang sangat penting dalam bidang ini.

Asymptotic Analysis ini sangat penting dalam analisis algoritma karena memungkinkan kita untuk memperkirakan kinerja algoritma pada input yang sangat besar. Contoh penerapan Asymptotic Analysis adalah pada algoritma sorting. Misalnya, algoritma Bubble Sort memiliki kompleksitas waktu O(n^2), yang berarti waktu eksekusi algoritma akan meningkat secara eksponensial saat jumlah elemen yang diurutkan semakin besar. Namun, algoritma Quick Sort memiliki kompleksitas waktu O(n log n), yang berarti waktu eksekusi algoritma akan meningkat secara logaritmik saat jumlah elemen yang diurutkan semakin besar.

2. Notasi Big-O

Notasi O digunakan untuk mengukur batas atas dari kompleksitas waktu suatu algoritma. Simbol O digunakan untuk menunjukkan notasi ini. Contohnya, jika kompleksitas waktu suatu algoritma adalah O, maka waktu eksekusi algoritma tersebut tidak akan melebihi n kali. Perhatikan beberapa contoh implementasi pada pemrograman bahasa Java.

1.    Implementasi O(1) (Waktu konstan)

Pada contoh diatas, waktu eksekusi metode printFirstElement tidak tergantung pada ukuran array. Waktu eksekusinya konstan, sehingga kompleksitasnya adalah O(1).

2.    Implementasi O (Waktu linier)

Pada contoh di atas, setiap elemen dalam array akan dicetak satu per satu. Jumlah iterasi bergantung pada ukuran array, sehingga kompleksitasnya adalah O.

3.    Implementasi O(n2) (Waktu kuadratik)

Pada contoh diatas, setiap elemen dalam array dipasangkan dengan setiap elemen lainnya. Jumlah iterasi adalah sebanyak kuadrat dari ukuran array, sehingga kompleksitasnya adalah O(n^2).

4.    Implementasi O(log n) (Waktu logaritmik)

Pada contoh diatas, metode binarySearch mengimplementasikan pencarian biner pada array yang diurutkan. Jumlah iterasi bergantung pada logaritma basis 2 dari ukuran array, sehingga kompleksitasnya adalah O(log n).

3. Notasi Omega

Notasi Omega disimbolkan dengan simbol Ω.  Notasi Omega digunakan untuk mengukur batas bawah dari kompleksitas waktu suatu algoritma. Contohnya, jika kompleksitas waktu suatu algoritma adalah Ω, maka waktu eksekusi algoritma tersebut tidak akan kurang dari n kali. Perhatikan contoh implementasi pada kasus mencari nilai minimum dalam sebuah larik bilangan bulat dengan bahasa pemrograman Java.

Dalam contoh di atas, kita menggunakan algoritma pencarian linear untuk mencari nilai minimum dalam larik bilangan bulat. Algoritma tersebut membandingkan setiap elemen dalam larik dengan nilai minimum yang saat ini diketahui, dan jika ditemukan nilai yang lebih kecil, maka nilai minimum diperbarui.

Ketika kita menganalisis kompleksitas waktu algoritma ini, kita dapat menggunakan notasi Ω untuk menunjukkan batas bawah pertumbuhan algoritma. Dalam kasus ini, algoritma pencarian linear memiliki kompleksitas Ω, dimana n adalah jumlah elemen dalam larik. Artinya, waktu eksekusi algoritma ini setidaknya sebanding dengan ukuran input, dan tidak lebih lambat dari konstanta kali n.

4. Notasi Theta

Notasi Theta disimbolkan dengan simbol Θ . Notasi Theta digunakan untuk mengukur batas atas dan batas bawah dari kompleksitas waktu suatu algoritma. Contohnya, jika kompleksitas waktu suatu algoritma adalah Θ, maka waktu eksekusi algoritma tersebut tidak akan melebihi atau kurang dari n kali. Perhatikan contoh kode pada bahasa pemrograman Java berikut ini.

Dalam contoh di atas, kita memiliki dua fungsi yang menggambarkan kompleksitas waktu berbeda. Fungsi linearTimeComplexity() memiliki kompleksitas Θ, dimana setiap elemen dalam larik akan dicetak satu kali. Fungsi quadraticTimeComplexity() memiliki kompleksitas Θ(n^2), dimana setiap elemen dalam larik akan dicetak sebanyak n kali. Dalam implementasi ini, kita dapat melihat bahwa jumlah iterasi dalam kedua fungsi berbanding lurus dengan ukuran input n, sesuai dengan notasi Θ yang digunakan untuk menggambarkan kompleksitas waktu algoritma.