Skip to main content

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:

  1. 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.
  2. 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.
  3. O(n) - Linear Time:

    • Waktu eksekusi algoritma tumbuh sebanding dengan ukuran masukan.
    • Contoh: Iterasi melalui semua elemen dalam sebuah array untuk mencari nilai tertentu.
  4. 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.
  5. O(n^2) - Quadratic Time:

    • Waktu eksekusi algoritma tumbuh sebanding dengan kuadrat dari ukuran masukan.
    • Contoh: Algoritma Bubble Sort, Insertion Sort untuk pengurutan.
  6. 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.
  7. O(2^n) - Exponential Time:

    • Waktu eksekusi algoritma tumbuh secara eksponensial seiring dengan ukuran masukan.
    • Contoh: Algoritma yang menggunakan pendekatan exhaustive search.
  8. 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.