IF Notes

Efisiensi Program dan Orders of Growth (Big-O)

5 min read

Back to IF5100 Pemrograman untuk Data Analitik

Efisiensi Program dan Orders of Growth (Big-O)

Questions/Cues

  • Mengapa efisiensi program tetap penting walau komputer semakin cepat?
  • Mengapa mengukur dengan timer (time) atau menghitung operasi masih belum cukup untuk membandingkan algoritma?
  • Apa beda best case, average case, dan worst case, dan mana yang biasanya dipakai?
  • Apa yang diukur oleh notasi Big O, dan mengapa kita memakai batas atas yang “ketat”?
  • Bagaimana aturan menyederhanakan ekspresi jumlah operasi menjadi Big O?

Reference Points

  • IF5100 — Algorithmic Complexity (Slides 2-19)

Mengapa Efisiensi Penting

Komputer memang cepat dan makin cepat, tetapi data set bisa sangat besar — misalnya Facebook (Juli 2022) melayani sekitar 2,934 miliar pengguna dengan sekitar 1 triliun edge/pertemanan; mencari secara brute force di data sebesar itu akan sangat lama. Solusi yang sederhana bisa saja tidak scalable terhadap ukuran data.

Efisiensi dipisah menjadi efisiensi waktu dan efisiensi ruang, dan keduanya sering berupa tradeoff: hasil dihitung lebih dulu lalu disimpan, kemudian diambil lewat lookup (contoh: memoization pada Fibonacci). Catatan ini fokus pada efisiensi waktu.

Tantangannya: satu program bisa diimplementasikan dalam banyak cara, sedangkan hanya ada sedikit algoritma berbeda untuk satu masalah. Kita ingin memisahkan pilihan implementasi dari pilihan algoritma yang lebih abstrak.

Tiga Cara Mengevaluasi Efisiensi

flowchart LR
    A["Metode 1<br/>Timer"] --> B["Metode 2<br/>Hitung operasi"]
    B --> C["Metode 3<br/>Order of growth<br/>Big O"]
    A -. "mengukur implementasi<br/>dan mesin" .-> D["Kurang cocok<br/>menilai algoritma"]
    B -. "bergantung implementasi" .-> D
    C -. "menilai algoritma<br/>dan skalabilitas" .-> E["Paling sesuai"]

Metode 1: Timer

Memakai modul time: catat waktu sebelum dan sesudah kode dijalankan, lalu ambil selisihnya. Kekurangannya, hasil tidak konsisten:

SifatTerpenuhi?
Waktu berbeda antar algoritma (yang kita inginkan)Ya
Waktu berbeda antar implementasiTidak diinginkan
Waktu berbeda antar komputerTidak diinginkan
Waktu tak bisa diprediksi dari input kecilTidak diinginkan
Hubungan input-waktu tak bisa dinyatakanTidak diinginkan

Metode 2: Menghitung Operasi

Asumsikan langkah berikut memakan waktu konstan: operasi matematika, perbandingan, assignment, dan mengakses objek di memori. Lalu hitung jumlah operasi sebagai fungsi ukuran input. Hasilnya bebas dari komputer dan bergantung pada algoritma, tetapi masih bergantung implementasi, tidak ada definisi jelas operasi mana yang dihitung, dan belum menyatakan hubungan input-waktu secara umum.

Metode 3: Order of Growth

Timer dan hitung operasi menilai implementasi (timer bahkan menilai mesin). Yang kita mau: menilai algoritma, menilai skalabilitas, dan menyatakannya dalam ukuran input. Karena itu kita tetap menghitung operasi, tetapi tidak peduli variasi kecil (mis. 3 atau 4 operasi primitif per iterasi) dan memperhatikan perilaku saat ukuran masalah membesar tanpa batas.

Memilih Input dan Kasus: Best, Average, Worst

Kita harus memutuskan “apa input-nya”: bisa sebuah integer (mysum(x)), panjang list (list_sum(L)), atau, jika ada beberapa parameter, Anda yang menentukan (mis. search_for_elmt(L, e)).

def search_for_elmt(L, e):
    for i in L:
        if i == e:
            return True
    return False
KasusDefinisiPada search_for_elmt
Best casewaktu minimum atas semua input berukuran len(L)e elemen pertama: konstan
Average caserata-rata waktu atas semua input berukuran len(L)memeriksa sekitar separuh elemen: ukuran praktis
Worst casewaktu maksimum atas semua input berukuran len(L)e tidak ada, seluruh list diperiksa: linear

Secara umum kita berfokus pada worst case.

Big O: Batas Atas Pertumbuhan

Big O (O()) mengukur batas atas pertumbuhan asimtotik, disebut order of growth.

  • Dipakai untuk worst case, karena kasus ini sering terjadi dan menjadi bottleneck.
  • Menyatakan laju pertumbuhan program relatif terhadap ukuran input.
  • Mengevaluasi algoritma, bukan mesin atau implementasi.
  • Cukup “order of”, bukan pertumbuhan eksak, tetapi batas atas harus seketat mungkin.

Contoh: fact_iter

def fact_iter(n):
    """assumes n an int >= 0"""
    answer = 1
    while n > 1:
        answer *= n
        n -= 1
    return answer

Jumlah operasi: 1 + 5n + 1. Kompleksitas asimtotik worst case: O(n), karena konstanta aditif diabaikan dan faktor pengali konstan diabaikan.

Aturan Penyederhanaan

Untuk sebuah jumlah suku, fokus pada suku yang tumbuh paling cepat (dominant term), dan abaikan faktor pengali konstan karena kita hanya ingin tahu seberapa cepat waktu naik ketika input membesar.

EkspresiBig O
n^2 + 2n + 2O(n^2)
n^2 + 100000n + 3^1000O(n^2)
log(n) + n + 4O(n)
0.0001*n*log(n) + 300nO(n log n)
2n^30 + 3^nO(3^n)

Summary

Efisiensi penting karena data bisa sangat besar, sehingga solusi sederhana belum tentu scalable; fokus catatan ini adalah efisiensi waktu (dengan tradeoff terhadap ruang, mis. memoization). Timer tidak konsisten antar implementasi/komputer/input, dan menghitung operasi masih bergantung implementasi, sehingga dipakai order of growth: menilai algoritma dan skalabilitas terhadap ukuran input. Perilaku dibedakan menjadi best, average, dan worst case, dengan fokus pada worst case. Big O adalah batas atas asimtotik yang ketat; untuk menyederhanakannya, buang konstanta aditif dan faktor pengali, lalu ambil dominant term (mis. 1 + 5n + 1 menjadi O(n)).

Graph View

Backlinks