Notasi Big-O

Apa itu notasi Big-O?

Notasi Big-O adalah cara menyatakan seberapa cepat kerja sebuah algoritma tumbuh ketika masukannya membesar, tanpa menghitung detik. Detik bergantung pada komputer, bahasa, dan harinya; banyaknya langkah dasar sebagai fungsi ukuran masukan n tidak. Jika algoritma memerlukan f(n) langkah, kita tulis f(n)=O(g(n)) bila f tumbuh tidak lebih cepat daripada g, sampai suatu faktor konstan.

Definisinya. f(n)=O(g(n)) berarti ada konstanta c>0 dan n_0 sehingga f(n)\le c· g(n)\qquaduntuk semua n\ge n_0. Pasangan (c,n_0) adalah saksi. Misalnya, f(n)=3n^2+5n+7 adalah O(n^2) dengan saksi c=4, n_0=7: untuk n\ge7 berlaku n^2-5n-7\ge0 (di n=7 nilainya 7, dan hanya membesar), yaitu 5n+7\le n^2, sehingga 3n^2+5n+7\le4n^2. c yang lain memberi n_0 yang lain: dengan c=3 tidak ada, karena 3n^2+5n+7>3n^2 selalu; dengan c=100 ketaksamaan berlaku dari n_0=1.

Apa yang dibuang. Faktor konstan (3n^2 dan 50n^2 keduanya O(n^2)) dan suku berorde rendah (n^2+1000n adalah O(n^2)), karena mesin menentukan yang pertama dan suku terbesar menentukan yang kedua ketika n besar. Dua aturan mengikutinya: jumlah beberapa fungsi didominasi yang tercepat, dan hasil kali mengalikan: O(n)+O(n^2)=O(n^2) dan O(n)· O(\log n)=O(n\log n).

Tiga lambang. O adalah batas atas ("pertumbuhan paling cepat sebesar ini"), \Omega adalah batas bawah (f(n)\ge c g(n) untuk n besar), dan \Theta keduanya: f=\Theta(g) berarti f=O(g) dan g=O(f). Pencarian linear adalah O(n), tetapi juga O(n^2) dan O(2^n), yang benar dan tidak berguna; pernyataan yang berguna adalah yang ketat, \Theta(n) pada kasus terburuk. Bila limit (f(n))/(g(n)) ada, ia menentukan: limit terhingga memberi f=O(g), limit terhingga tak nol memberi f=\Theta(g), dan limit 0 berarti f tumbuh jauh lebih lambat (di sinilah Aturan L'Hôpital dipakai).

Cobalah definisinya di bawah. Ketik dua fungsi dengan n ditulis x, pilih c, dan widget mencari ambang n_0.

Seberapa cepat laju pertumbuhan yang umum tumbuh?

Segelintir kelas mencakup hampir setiap algoritma yang kamu temui, dan masing-masing adalah dunia yang berbeda tentang apa yang layak. Dari pertumbuhan paling lambat ke paling cepat:

Urutannya 1≪\log n≪√ n≪ n≪ n\log n ≪ n^2≪ n^3≪2^n≪ n!, dengan f≪ g berarti \frac fg→0; perbandingan pertumbuhan yang sama, logaritma di bawah pangkat mana pun di bawah eksponensial, dibuktikan dengan limit dalam artikel laju pertumbuhan dan Aturan L'Hôpital.

Arti kelas itu dalam waktu. Ambil komputer yang melakukan 10^9 langkah per detik. Untuk n=100 algoritma kuadratik memerlukan 10^4 langkah, sepuluh mikrodetik. Yang eksponensial memerlukan 2^100≈1,3×10^30 langkah, sekitar 4×10^13 tahun, ribuan kali usia alam semesta. Dan masukan terbesar yang selesai dalam satu detik sekitar 10^9 untuk n, 4×10^7 untuk n\log n, 31 622 untuk n^2, 1000 untuk n^3, hanya 29 untuk 2^n dan 12 untuk n!. Komputer seribu kali lebih cepat hanya menambah 10 pada n algoritma eksponensial (2^10≈1000), sedangkan ia mengalikan n algoritma linear dengan seribu. Itulah sebabnya kelas lebih penting daripada mesin.

Geser n dan kecepatan di bawah. Tabel memberi langkah, waktu, dan n terbesar untuk anggaran waktu.

Bagaimana mencari kompleksitas waktu sebuah kode?

Kamu menghitung langkah dasar, lalu hanya menyimpan suku yang tumbuh paling cepat. Beberapa aturan mencakup kebanyakan kode:

1. Operasi dasar berbiaya 1: penugasan, perbandingan, operasi aritmetika, membaca elemen larik.
2. Pernyataan berurutan menjumlahkan, dan yang terbesar menang: perulangan n langkah diikuti perulangan n^2 langkah adalah O(n+n^2)=O(n^2).
3. Perulangan mengalikan: banyak iterasi kali biaya badannya. Dua perulangan bersarang atas n berbiaya n· n=n^2.
4. Perulangan ganda segitiga (j dari i+1 sampai n) berjalan \fracn(n-1)2 kali, yang tetap O(n^2).
5. Perulangan yang membagi dua atau menggandakan penghitungnya berjalan \log_2n kali: while n > 1: n //= 2 memerlukan \lfloor\log_2n\rfloor langkah, demikian pula i *= 2 selama i < n.
6. Perulangan sampai √ n (while i * i <= n) berjalan \lfloor√ n\rfloor kali.
7. Fungsi rekursif menghasilkan rekurensi, diselesaikan pada bagian berikutnya; dua panggilan rekursif berukuran n-1 memberi 2^n.
8. Kondisi berbiaya cabang yang lebih mahal, bila kamu menginginkan kasus terburuk.

Menghitung dengan percobaan. Kebiasaan baik adalah membiarkan program menghitung langkahnya sendiri dan menggandakan n: jika hitungannya berlipat dua algoritmanya linear; jika berlipat empat, kuadratik; jika bertambah konstan, logaritmik; jika berlipat sedikit lebih dari dua, ia n\log n. Widget di bawah menjalankan dua belas algoritma pada masukan kasus terburuk, dan kolom rasio memperlihatkan persis hal ini.

def first(a):                 # O(1): one step, whatever the length
    return a[0]


def total(a):                 # O(n): one pass
    s = 0
    for x in a:
        s += x
    return s


def pairs(a):                 # O(n^2): n(n - 1)/2 pairs
    count = 0
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            count += 1
    return count


def powers(n):                # O(log n): i doubles until it passes n
    i = 1
    while i < n:
        i *= 2
    return i


def is_prime(n):              # O(sqrt n) divisions, but exponential in the number of digits of n
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return n > 1

Apa itu kasus terbaik, terburuk, rata-rata, dan biaya teramortisasi?

Algoritma yang sama dapat berbiaya berbeda pada masukan berbeda dengan ukuran yang sama, sehingga kompleksitas selalu dinyatakan untuk suatu kasus: terbaik, terburuk, atau rata-rata. Secara bawaan "kompleksitas" berarti kasus terburuk, karena ia adalah jaminan.

• Pencarian linear sebuah nilai dalam daftar n: terbaik 1 perbandingan (elemen pertama), terburuk n (ia terakhir atau tidak ada), rata-rata sekitar (n+1)/(2) jika ia ada dan setiap posisi sama mungkin. Terbaik \Theta(1), terburuk dan rata-rata \Theta(n).
• Insertion sort: kasus terbaik n-1 perbandingan (sudah terurut), kasus terburuk (n(n-1))/(2) (terbalik). Kode yang sama O(n) atau O(n^2) tergantung masukannya.
• Quicksort: rata-rata O(n\log n), tetapi O(n^2) pada kasus terburuk, ketika pivotnya selalu elemen terkecil atau terbesar.
• Pencarian tabel hash: O(1) rata-rata dan O(n) jika setiap kunci bertabrakan.

Biaya teramortisasi. Beberapa operasi biasanya murah dan sesekali mahal, dan yang penting adalah totalnya pada barisan panjang. Larik dinamis (list Python, vector C++) menggandakan kapasitasnya ketika penuh: penyalinan berbiaya 1+2+4+…+2^k<2·2^k, sehingga n penambahan berbiaya kurang dari 3n langkah seluruhnya, dan setiap penambahan O(1) teramortisasi walaupun salah satunya berbiaya O(n).

Kompleksitas ruang adalah gagasan yang sama untuk memori: merge sort memerlukan ruang tambahan O(n), pengurutan di tempat seperti heapsort O(1), dan rekursi berkedalaman d memakai tumpukan O(d). Big-O menggambarkan memori seperti menggambarkan waktu.

Batas bawah. \Omega dapat menunjukkan bahwa tidak ada algoritma yang lebih baik. Pengurutan dengan perbandingan memerlukan sedikitnya \log_2(n!)≈ n\log_2n-1,44n perbandingan, karena n! urutan yang mungkin harus dibedakan dengan jawaban ya atau tidak, sehingga \Omega(n\log n); merge sort mencapainya, sehingga ia \Theta(n\log n) dan optimal di antara pengurutan perbandingan.

Bagaimana menyelesaikan rekurensi sebuah algoritma rekursif?

Algoritma rekursif yang memecah masalah berukuran n menjadi a submasalah berukuran n/b dan melakukan kerja n^d untuk memecah dan menggabungkan memiliki biaya T(n)=aT(n/b)+n^d, dan teorema Master menyelesaikannya dengan membandingkan d dengan \log_ba.

Merge sort, diurai. T(n)=2T(n/2)+n. Tingkat teratas melakukan kerja n. Tingkat berikutnya punya 2 masalah berukuran n/2, masing-masing \frac n2, lagi-lagi n seluruhnya; tingkat sesudahnya punya 4 masalah berukuran \frac n4, lagi-lagi n. Setiap tingkat berbiaya n, dan ada \log_2n tingkat (membagi dua n sampai 1), sehingga T(n)=n\log_2n+n=\Theta(n\log n).

Teorema Master. Untuk T(n)=aT(n/b)+\Theta(n^d) dengan a\ge1, b>1, dan d\ge0, misalkan \rho=(a)/(b^d) adalah rasio kerja pada satu tingkat terhadap kerja di tingkat di atasnya: - jika d>\log_ba (\rho<1) kerja menyusut ke bawah pohon dan puncaknya mendominasi: T(n)=\Theta(n^d); - jika d=\log_ba (\rho=1) setiap tingkat berbiaya sama: T(n)=\Theta(n^d\log n); - jika d<\log_ba (\rho>1) kerja membesar ke bawah pohon dan daun-daunnya mendominasi: T(n)=\Theta\left(n^\log_ba\right).

Untuk n=b^k jumlahnya eksak: T(b^k)=n^d\left(1+\rho+\rho^2+…+\rho^k\right) bila setiap daun berbiaya 1, dan ketiga kasus adalah tiga perilaku deret geometri.

Contoh. - Pencarian biner: T(n)=T(n/2)+1, sehingga a=1, b=2, d=0=\log_21: \Theta(\log n). - Merge sort: a=b=2, d=1=\log_22: \Theta(n\log n). - Perkalian bilangan dengan Karatsuba: T(n)=3T(n/2)+n, d=1<\log_23≈1,585: \Theta\left(n^1,585\right), lebih baik daripada n^2 cara sekolah. - Perkalian matriks dengan membagi menjadi 8 blok: T(n)=8T(n/2)+n^2, \log_28=3>2: \Theta(n^3); trik Strassen dengan 7 perkalian, \log_27≈2,807, memberi \Theta\left(n^2,807\right). - Membagi dua lalu bekerja n: T(n)=T(n/2)+n, d=1>\log_21=0: \Theta(n).

Rekurensi yang tidak berbentuk ini memerlukan metode lain. T(n)=T(n-1)+n terurai menjadi (n(n+1))/(2)=\Theta(n^2), dan T(n)=T(n-1)+T(n-2)+1, banyaknya panggilan fungsi Fibonacci naif, tumbuh seperti φ^n dengan φ=\frac1+√52≈1,618.

Pilih a, b, dan d di bawah. Tabel menghitung T(n) secara eksak untuk n=b^k dan membaginya dengan pertumbuhan yang diramalkan: kolom terakhir menuju konstanta.

Apa yang tidak dikatakan Big-O?

Big-O membandingkan pertumbuhan untuk n besar, sehingga ia tidak mengatakan apa pun tentang masukan kecil, faktor konstan, memori, atau mesin.

• Konstanta penting untuk n kecil. 100n adalah O(n) dan n^2 adalah O(n^2), namun n^2<100n untuk setiap n<100. Pustaka pengurutan nyata berupa hibrida: pengurutan Python dan Java (Timsort) memakai insertion sort, kuadratik pada kasus terburuk, untuk bagian pendek, karena dengan konstanta yang sangat kecil ia mengalahkan metode n\log n di bawah beberapa puluh elemen.
• Tidak semua langkah berbiaya sama. Langkah yang meleset dari cache prosesor dapat berbiaya seratus kali langkah yang mengenainya. Dua perulangan O(n), satu membaca memori berurutan dan satu melompat-lompat, dapat berbeda satu orde besaran.
• Apa itu n. n adalah ukuran masukan, banyaknya bit atau angka yang diperlukan untuk menuliskannya, bukan nilainya. Pembagian coba-coba, while i * i <= n, memerlukan O(√ N) pembagian untuk menguji bilangan N, tetapi N memiliki n=\log_2N bit (lihat berapa nilai yang dapat dimuat bit), sehingga biayanya O\left(2^n/2\right): eksponensial terhadap ukuran masukan, itulah sebabnya menguji bilangan 600 angka dengan pembagian coba-coba tidak ada harapan.
• Biaya tersembunyi operasi. x in a_list adalah O(n) tetapi x in a_set adalah O(1) rata-rata; s += "a" pada string dapat menyalin seluruh string; list.insert(0, x) menggeser setiap elemen, O(n), sedangkan list.append(x) adalah O(1) teramortisasi; sorted(a) adalah O(n\log n).
• Kasus terburuk mungkin tidak lazim. Kasus terburuk quicksort adalah n^2 dan tidak ada yang keberatan, karena ia hampir tidak pernah terjadi dengan pivot acak.

Pakai Big-O untuk memilih antara gagasan n^2 dan n\log n sebelum menulis kode, dan pengukuran untuk memilih antara dua gagasan yang sekelas.

Bagaimana mengukur kompleksitas dalam kode?

Hitung langkahnya, jangan mengukur waktunya: penghitung itu eksak, dapat diulang, dan tidak bergantung pada komputer. Program di bawah menghitung perbandingan pencarian linear, pencarian biner, dan bubble sort untuk masukan 250, 500, dan 1000 elemen, panggilan fungsi Fibonacci dengan dan tanpa memo, dan iterasi perulangan ganda dan perulangan pembagian dua. Menggandakan n menambah satu pada pencarian biner, melipatduakan pencarian linear, dan melipatempatkan bubble sort.

def linear(a, target):
    """Comparisons made while looking for target in a list."""
    steps = 0
    for x in a:
        steps += 1
        if x == target:
            break
    return steps


def binary(a, target):
    """Comparisons made by binary search in a sorted list."""
    lo, hi, steps = 0, len(a) - 1, 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if a[mid] == target:
            return steps
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return steps


def bubble(a):
    """Comparisons made by bubble sort."""
    a, steps = list(a), 0
    for i in range(len(a) - 1):
        for j in range(len(a) - 1 - i):
            steps += 1
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return steps


def fib_calls(n, memo=None):
    """Calls made by fib(n), without and with a dictionary of known values."""
    calls = 0

    def fib(k, known):
        nonlocal calls
        calls += 1
        if k < 2:
            return k
        if known is not None and k in known:
            return known[k]
        value = fib(k - 1, known) + fib(k - 2, known)
        if known is not None:
            known[k] = value
        return value

    fib(n, memo)
    return calls


for n in (250, 500, 1000):
    a = list(range(n))
    print(n, linear(a, -1), binary(a, -1), bubble(a[::-1]))
print(fib_calls(20), fib_calls(20, {}))
print(2 ** 100 / 1e9 / (365.25 * 24 * 3600))
# 250 250 7 31125
# 500 500 8 124750
# 1000 1000 9 499500
# 21891 39
# 40169423537538.64

const count = (f, n) => {
  let steps = 0
  f(n, () => steps++)
  return steps
}
const pairs = (n, tick) => { for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) tick() }
const halving = (n, tick) => { while (n > 1) { n = Math.floor(n / 2); tick() } }
const subsets = (n, tick) => { const go = (i) => { if (i === n) return tick(); go(i + 1); go(i + 1) }; go(0) }
const c = [1000, 2000, 4000].map((n) => count(pairs, n))
c                                           // [499500, 1999000, 7998000]
c.map((v, i) => (i ? v / c[i - 1] : null))  // [null, 4.002..., 4.001...]: doubling n quadruples a quadratic count
;[1e3, 1e6, 1e9].map((n) => count(halving, n))   // [9, 19, 29]: a thousand times more input adds about 10 steps
;[10, 14, 18].map((n) => count(subsets, n))      // [1024, 16384, 262144]: four more elements, sixteen times the work

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
  for (int n = 100; n <= 400; n = n * 2) {
    int pairs = 0;
    for (int i = 0; i < n; i++)
      for (int j = i + 1; j < n; j++) pairs++;           // n(n - 1)/2 steps
    int halves = 0;
    for (int m = n; m > 1; m = m / 2) halves++;          // about log2(n) steps
    printf("%d %d %d\n", n, pairs, halves);
  }
  return 0;
}

/* output:
100 4950 6
200 19900 7
400 79800 8
*/

Dari mana notasi Big-O berasal?

Big-O bermula dalam teori bilangan, jauh sebelum komputer, sebagai cara menyatakan seberapa besar suku galat.

• 1894. Matematikawan Jerman Paul Bachmann memperkenalkan huruf O dalam bukunya tentang teori bilangan analitik, untuk Ordnung, orde, sebuah suku.
• 1909. Edmund Landau memakainya dan menambahkan o kecil ("tumbuh jauh lebih lambat"), dan notasi itu masih sering disebut notasi Landau.
• 1914. G. H. Hardy dan J. E. Littlewood memperkenalkan \Omega untuk batas bawah pertumbuhan.
• 1965. Juris Hartmanis dan Richard Stearns menerbitkan On the computational complexity of algorithms, yang mengukur waktu suatu komputasi dan mendirikan teori kompleksitas komputasi.
• 1968 dan 1976. Donald Knuth memakai O untuk analisis algoritma dalam The Art of Computer Programming, dan pada 1976 mendefinisikan ulang \Omega dan memperkenalkan \Theta sebagai batas ketat, memberi ketiga lambang itu arti yang mereka miliki dalam ilmu komputer sekarang.
• 1971–1972. Stephen Cook dan Richard Karp mendefinisikan NP-lengkap, pertanyaan masalah mana yang dapat diselesaikan dalam waktu polinomial sama sekali: garis antara O(n^k) dan eksponensial yang digambar artikel ini dalam tabel laju pertumbuhan.

Kesalahan apa yang sering terjadi pada Big-O?

Kesalahan paling umum pada Big-O adalah sembilan hal berikut, masing-masing dengan pernyataan yang benar.

Latihan: uji pemahamanmu

Soal-soal ini mencampur semua yang dibahas di atas. Jika jawabanmu belum tepat, perhatikan petunjuk yang tersedia, lalu coba kembali.

Ringkasan: notasi Big-O sekilas

• Definisi: f=O(g) jika f(n)\le c g(n) untuk semua n\ge n_0; \Omega batas bawah, \Theta yang ketat.
• Buang konstanta dan suku rendah: 3n^2+5n+7=O(n^2).
• Urutan: 1≪\log n≪√ n≪ n≪ n\log n ≪ n^2≪ n^3≪2^n≪ n!; kelas lebih penting daripada mesin.
• Menghitung: urutan menjumlahkan, perulangan mengalikan, pembagian dua memberi \log n, rekursi memberi rekurensi; gandakan n dan lihat rasionya.
• Kasus: sebut terbaik, terburuk, atau rata-rata; biaya teramortisasi menyebarkan langkah mahal yang jarang ke banyak langkah murah.
• Teorema Master: T(n)=aT(n/b)+n^d membandingkan d dengan \log_ba: \Theta(n^d), \Theta(n^d\log n), atau \Theta(n^\log_ba).
• Batas Big-O: konstanta untuk n kecil, memori, ukuran masukan adalah angkanya, dan biaya tersembunyi operasi.
• Berikutnya: pencarian atau pengurutan dengan langkah yang dihitung.
• Kode: hitung langkah dengan penghitung, jangan mengukur waktu.

Glosarium: istilah penting

Notasi Big-O

Cara menyatakan bahwa suatu fungsi tumbuh tidak lebih cepat daripada fungsi lain, sampai faktor konstan dan untuk masukan besar.

Kompleksitas waktu

Banyaknya langkah dasar yang diambil sebuah algoritma, sebagai fungsi ukuran masukannya.

Big Theta

Batas ketat: suatu fungsi dibatasi dari atas dan dari bawah oleh kelipatan konstan dari fungsi yang sama.

Kasus terburuk

Masukan berukuran tertentu yang membuat algoritma mengambil langkah terbanyak, yang memberi jaminan.

Biaya teramortisasi

Biaya rata-rata per operasi pada barisan panjang, ketika operasi mahal jarang dan operasi murah sering.

Relasi rekurensi

Persamaan yang memberi biaya masalah berukuran n dalam biaya masalah yang lebih kecil.

Teorema Master

Aturan untuk menyelesaikan rekurensi berbentuk T(n) = aT(n/b) + n pangkat d dengan membandingkan d dengan logaritma a berbasis b.

Kompleksitas ruang

Banyaknya memori tambahan yang diperlukan sebuah algoritma, sebagai fungsi ukuran masukannya.

Pertanyaan yang sering diajukan

Referensi

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2022). Introduction to Algorithms (4th ed.), chapters 3 and 4: Characterizing Running Times; Divide-and-Conquer. MIT Press.
2. Donald E. Knuth (1976). Big Omicron and big Omega and big Theta. ACM SIGACT News 8(2).
3. Juris Hartmanis and Richard E. Stearns (1965). On the computational complexity of algorithms. Transactions of the American Mathematical Society 117.
4. Paul Bachmann (1894). Analytische Zahlentheorie. Teubner, Leipzig.

Artikel terkait

• Bilangan Floating-Point: Cara kerja bilangan floating-point: bit IEEE 754, jarak dan pembulatan, NaN dan tak hingga, galat yang menumpuk, pembatalan, perbandingan, dan tipe yang dipakai.
• Bentuk Tak Tentu dan Aturan L’Hôpital: Aturan L’Hôpital dan bentuk tak tentu 0/0, ∞/∞, 0·∞, ∞−∞, 1^∞, 0^0, dan ∞^0: cara memakainya, kapan gagal, dan buktinya dengan teorema Cauchy, dengan kode.
• Bilangan Biner: Konversi, Operasi, Bit, dan Komplemen Dua: Bilangan biner: bit dan nilai tempat, konversi ke desimal dan heksadesimal, aritmetika biner, komplemen dua, operator bitwise, dan pecahan biner.
• Barisan dan Deret Geometri: Rasio, Jumlah, dan Pertumbuhan: Barisan dan deret geometri: rasio, rumus suku ke-n, jumlah berhingga dan tak hingga, rata-rata geometri, bunga majemuk, dan peluruhan, dengan latihan.