Analisis Big O
Analisis Big O digunakan untuk mengevaluasi kompleksitas waktu (dan kadang-kadang ruang) dari algoritma. Berikut adalah beberapa analisis Big O umum yang sering digunakan:
-
O(1) - Constant Time:
- Algoritma memiliki waktu eksekusi yang tetap, tidak peduli berapa banyak data yang diolah.
- Contoh: Mengakses elemen tertentu dalam array dengan indeks.
-
O(log n) - Logarithmic Time:
- Waktu eksekusi algoritma meningkat secara logaritmik seiring dengan pertumbuhan ukuran masukan.
- Contoh: Pencarian biner di sebuah array yang sudah diurutkan.
-
O(n) - Linear Time:
- Waktu eksekusi algoritma tumbuh sebanding dengan ukuran masukan.
- Contoh: Iterasi melalui semua elemen dalam sebuah array untuk mencari nilai tertentu.
-
O(n log n) - Linearithmic Time:
- Waktu eksekusi algoritma tumbuh sebanding dengan produk dari ukuran masukan dan logaritmik dari ukuran masukan.
- Contoh: Beberapa algoritma pengurutan seperti Merge Sort, Quick Sort.
-
O(n^2) - Quadratic Time:
- Waktu eksekusi algoritma tumbuh sebanding dengan kuadrat dari ukuran masukan.
- Contoh: Algoritma Bubble Sort, Insertion Sort untuk pengurutan.
-
O(n^k) - Polynomial Time (untuk k > 1):
- Waktu eksekusi algoritma tumbuh sebanding dengan pangkat k dari ukuran masukan.
- Contoh: Algoritma pengurutan dengan kompleksitas O(n^3) seperti algoritma Selection Sort.
-
O(2^n) - Exponential Time:
- Waktu eksekusi algoritma tumbuh secara eksponensial seiring dengan ukuran masukan.
- Contoh: Algoritma yang menggunakan pendekatan exhaustive search.
-
O(n!) - Factorial Time:
- Waktu eksekusi algoritma tumbuh secara faktorial dengan ukuran masukan.
- Contoh: Algoritma yang menggunakan pendekatan exhaustive search seperti Traveling Salesman Problem dengan brute force.
Analisis Big O ini membantu programmer untuk memprediksi bagaimana kinerja algoritma akan berubah seiring dengan peningkatan ukuran masukan, dan memilih algoritma yang tepat berdasarkan kompleksitas yang diinginkan untuk aplikasi yang sedang dikembangkan.