Intuisi Big-O

Notasi Big-O, ditulis $O(\cdot)$, menyatakan kelas pertumbuhan banyaknya operasi sebuah algoritma ketika banyaknya data $n$ bertambah, tanpa mempedulikan kecepatan mesin maupun detail pemrogramannya. Intuisinya dapat dibangun tanpa matematika berat dengan cara menghitung operasi secara langsung, misalnya banyaknya perbandingan pada pengurutan atau banyaknya pemeriksaan pada pencarian. Angka tersebut sama di setiap mesin dan setiap eksekusi. Topik ini mengukur pertumbuhan algoritma pengurutan dan pencarian yang telah dibangun pada modul ini melalui penghitungan operasi, lalu menata hasilnya ke dalam kelas-kelas Big-O yang paling sering ditemui.

Menghitung operasi alih-alih mengukur waktu#

Mengukur waktu eksekusi memang terasa alami, tetapi angkanya berubah pada setiap eksekusi karena pengaruh beban mesin, cache, dan pengoptimalan kompilator. Penghitung operasi justru deterministik, yaitu jumlah perbandingan atau jumlah pemeriksaan tetap sama selama datanya sama, sehingga cocok untuk perbandingan antaralgoritma. Program berikut menghitung perbandingan bubble sort dan insertion sort pada data acak tetap. Pencarian linier dan biner juga dihitung dengan mencari nilai yang tidak ada, sehingga kasus terburuknya selalu terjadi.

Data acak pada program dibangun dari pola tetap (i * 37) % n, bukan dari rand(), sehingga permutasinya identik pada setiap eksekusi dan siapa pun dapat menghitung ulang angka pada keluaran.

#include <stdio.h>

#define BANYAK_UJI 3
#define MAKS 1000

int ukuran[BANYAK_UJI] = {10, 100, 1000};

int hitung_bubble(int *a, int n)
{
    int perbandingan = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            perbandingan = perbandingan + 1;
            if (a[j] > a[j + 1]) {
                int sementara = a[j];
                a[j] = a[j + 1];
                a[j + 1] = sementara;
            }
        }
    }
    return perbandingan;
}

int hitung_insertion(int *a, int n)
{
    int perbandingan = 0;
    for (int i = 1; i < n; i++) {
        int kunci = a[i];
        int j = i - 1;
        while (j >= 0) {
            perbandingan = perbandingan + 1;
            if (a[j] > kunci) {
                a[j + 1] = a[j];
                j = j - 1;
            } else {
                break;
            }
        }
        a[j + 1] = kunci;
    }
    return perbandingan;
}

int cari_linier(const int *a, int n, int target)
{
    int perbandingan = 0;
    for (int i = 0; i < n; i++) {
        perbandingan = perbandingan + 1;
        if (a[i] == target) {
            return perbandingan;
        }
    }
    return perbandingan;
}

int cari_biner(const int *a, int n, int target)
{
    int perbandingan = 0;
    int rendah = 0;
    int tinggi = n - 1;
    while (rendah <= tinggi) {
        perbandingan = perbandingan + 1;
        int tengah = rendah + (tinggi - rendah) / 2;
        if (a[tengah] == target) {
            return perbandingan;
        }
        if (a[tengah] < target) {
            rendah = tengah + 1;
        } else {
            tinggi = tengah - 1;
        }
    }
    return perbandingan;
}

int main(void)
{
    static int data[MAKS];
    static int salinan[MAKS];

    printf("    n | bubble  | insertion | linier | biner\n");
    printf("-----+---------+-----------+--------+-------\n");

    for (int u = 0; u < BANYAK_UJI; u++) {
        int n = ukuran[u];

        /* pola tetap (i * 37) % n memberi permutasi yang sama di setiap eksekusi */
        for (int i = 0; i < n; i++) {
            data[i] = (i * 37) % n;
        }

        for (int i = 0; i < n; i++) {
            salinan[i] = data[i];
        }
        int jumlah_bubble = hitung_bubble(salinan, n);

        for (int i = 0; i < n; i++) {
            salinan[i] = data[i];
        }
        int jumlah_insertion = hitung_insertion(salinan, n);

        /* nilai -1 tidak pernah ada pada data, sehingga kasus terburuk selalu terjadi */
        int jumlah_linier = cari_linier(data, n, -1);
        int jumlah_biner = cari_biner(data, n, -1);

        printf("%5d | %7d | %9d | %6d | %5d\n",
               n, jumlah_bubble, jumlah_insertion, jumlah_linier, jumlah_biner);
    }
    return 0;
}

    n | bubble  | insertion | linier | biner
-----+---------+-----------+--------+-------
   10 |      45 |        27 |     10 |     3
  100 |    4950 |      2547 |    100 |     6
 1000 |  499500 |    252747 |   1000 |     9

Tabel keluaran memperlihatkan empat pola sekaligus. Perbandingan bubble sort naik sekitar seratus kali lipat setiap kali $n$ naik sepuluh kali lipat, dan pola seratus kali lipat itu adalah tanda kelas $O(n^2)$. Perbandingan insertion sort ikut naik seratus kali lipat dengan angka yang lebih kecil, sehingga kelasnya sama tetapi faktor konstantanya lebih hemat. Pemeriksaan pencarian linier mengikuti $n$ dengan tepat. Pencarian biner hanya naik dari 3 menjadi 6 lalu 9, yaitu menambah kira-kira tiga langkah setiap kali data dikalikan sepuluh. Itulah tanda kelas $O(\log n)$.

Kelas pertumbuhan yang sering ditemui#

Kelas Big-O memberi nama pada pola pertumbuhan tersebut, dan urutan kasarannya dari paling lambat tumbuh adalah $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, lalu $O(n^2)$. Grafik berikut menggambar tiga di antaranya pada skala yang sama, dan jarak antarkurvanya melebar begitu cepat sehingga perbedaan kelas mengalahkan segala perbedaan kecepatan mesin.

Tabel berikut memetakan setiap kelas ke operasi yang sudah ditemui pada modul ini, sehingga angka-angka keluaran program tadi dapat dipasangkan dengan namanya.

Membaca grafik dengan teliti menghasilkan kesimpulan yang tidak terasa dari angka tunggal. Pada $n$ yang kecil, ketiga kurva masih berdesakan di dasar grafik, sehingga algoritma $O(n^2)$ pun terasa seketika. Sebaliknya pada $n$ yang besar, kurva $O(n^2)$ menyisakan kelas lain jauh di bawah, dan inilah alasan merge sort dipilih untuk data besar meskipun persiapannya lebih rumit daripada insertion sort.

Konstanta dan kasus terbaik hingga terburuk#

Big-O membuang faktor konstanta, sehingga dua algoritma dalam satu kelas tetap dapat berbeda beberapa kali lipat pada praktiknya. Keluaran program di atas menunjukkan contohnya, yaitu insertion sort membutuhkan sekitar separuh perbandingan bubble sort untuk data yang sama karena penggeserannya berhenti begitu menemukan tempat yang pas. Selisih konstanta seperti ini tetap berguna ketika pilihan lain sudah tidak mungkin. Namun, selisih itu tidak pernah mengalahkan lompatan kelas. $O(n \log n)$ pada data seratus ribu masih jauh lebih cepat daripada $O(n^2)$ yang konstantanya lebih kecil.

Kelas Big-O lazim dilaporkan untuk kasus terburuk, sedangkan kasus terbaik dan rata-rata bisa jauh lebih baik. Insertion sort pada data yang sudah terurut hanya melakukan satu perbandingan per elemen, sehingga kasus terbaiknya $O(n)$. Quick sort dengan poros yang buruk justru merosot menjadi $O(n^2)$. Karena itu, kebiasaan yang baik adalah menanyakan tiga hal sekaligus, yaitu kelas terburuknya, sebaran kasusnya, dan ukuran data yang diharapkan, sebelum menyimpulkan algoritma mana yang lebih tepat.

Kesalahan umum#

Lima kebiasaan berikut merusak keabsahan perbandingan yang baru dibangun, dan sebagian besar berpola pada sumber angka yang tidak stabil.

• Menyandingkan waktu nyata sebagai bukti kelas. Angka detik berubah pada setiap eksekusi dan tidak dapat direproduksi. Gunakan penghitung operasi yang deterministik, atau ulangi pengukuran waktu berkali-kali dengan data yang sama.
• Menggunakan rand() tanpa benih tetap. Data uji yang berubah setiap eksekusi membuat angka perbandingannya tidak dapat dihitung ulang. Bangun data dari pola tetap atau tetapkan benihnya secara eksplisit.
• Membaca kasus terbaik sebagai janji umum. Insertion sort yang seketika pada data terurut tetap $O(n^2)$ pada data acak. Laporkan kelas beserta kasusnya, bukan satu angka yang paling mengesankan.
• Pencarian biner tanpa data terurut. Kelas $O(\log n)$ hanya berlaku pada data terurut, dan algoritma yang berjalan di atas data acak melaporkan hasil yang salah tanpa pesan error apa pun.
• Menyimpulkan kelas dari satu ukuran data. Dua titik ukuran sudah membedakan konstanta dari kelas, tetapi tiga titik yang berjarak sepuluh kali lipat baru benar-benar memperlihatkan polanya. Uji pada 10, 100, dan 1000 sebagaimana program di atas.

Ringkasan#

• Big-O menyatakan kelas pertumbuhan operasi terhadap $n$, dan penghitungan perbandingan memberi bukti empiris yang deterministik tanpa pengukuran waktu.
• Keluaran penghitungan memperlihatkan pola kelasnya, yaitu $O(n^2)$ melipatgandakan seratus kali saat $n$ dikalikan sepuluh, $O(n)$ mengikuti $n$, dan $O(\log n)$ hanya menambah beberapa langkah.
• Faktor konstanta memengaruhi kecepatan di dalam satu kelas, sedangkan perbedaan kelas menentukan pemenangnya pada data besar.

Referensi#

• Sorting — VisuAlgo — Visualisasi yang menghitung jumlah perbandingan dan pertukaran tiap algoritma pengurutan.
• bsearch(3) — Linux man-pages project — Pencarian biner pustaka standar yang perilakunya dihitung pada topik ini.