Big O Notation: What A-Level CS Actually Expects

Notasi Big O muncul di setiap spec computer science A-level utama (AQA, OCR, Edexcel) dan banyak siswa terjebak bukan karena matematikanya sulit, tetapi karena mereka tidak pernah melihatnya terikat pada kode sebenarnya. Ini adalah penjelasan praktis tentang apa yang perlu Anda ketahui dan cara menjawab pertanyaan ujian padanya tanpa bertele-tele.

Apa yang sebenarnya diukur Big O

Big O menjelaskan bagaimana waktu berjalan (atau penggunaan memori) dari suatu algoritma berkembang seiring ukuran input, biasanya disebut n, menjadi lebih besar. Ini bukan pengukuran stopwatch dalam detik. Ini adalah cara menjelaskan tingkat pertumbuhan sehingga Anda dapat membandingkan algoritma terlepas dari perangkat keras.

Ketika Anda menulis O(n), Anda mengatakan: jika saya menggandakan input, pekerjaan kira-kira menggandakan. O(n²) berarti menggandakan input kira-kira melipatgandakan pekerjaan. Hubungan itu adalah apa yang ingin diidentifikasi pemeriksa, bukan penghitungan operasi yang tepat.

Kompleksitas yang perlu Anda kuasai

Untuk A-level, ini adalah yang muncul lagi dan lagi:

• O(1) – waktu konstan. Mengakses elemen larik menurut indeks: arr[5]. Tidak peduli seberapa besar lariknya.
• O(log n) – logaritmik. Pencarian biner pada daftar terurut. Setiap langkah membagi dua ruang pencarian yang tersisa.
• O(n) – linear. Satu loop melalui daftar, seperti pencarian linear yang memeriksa setiap item sekali.
• O(n log n) – linearitmik. Merge sort dan quicksort (kasus rata-rata) berada di sini.
• O(n²) – kuadrat. Loop bersarang atas data yang sama, yang persis apa yang dilakukan bubble sort, insertion sort, dan selection sort.
• O(2ⁿ) – eksponensial. Fibonacci rekursif naif tanpa memoisation. Menjadi kacau dengan cepat.

Anda harus dapat melihat pseudocode dan mengatakan mana dari ini pada pandangan pertama, karena itu sebagian besar yang diuji.

Membaca kode untuk kompleksitas

Metode yang selalu berhasil: hitung loop dan lihat bagaimana hubungannya dengan n.

# O(n) - satu loop, satu pass
for i in range(n):
    print(i)

# O(n^2) - loop bersarang, keduanya terikat pada n
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - ruang pencarian membagi dua setiap iterasi
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

Loop bersarang di mana jangkauan loop dalam bergantung pada n tetap O(n²), bahkan jika terlihat sedikit berbeda (seperti for j in range(i) bukan for j in range(n) — itu masih kuadrat secara keseluruhan, hanya dengan perbedaan faktor konstan).

Hati-hati dengan loop yang tidak bergantung pada n sama sekali. Loop yang selalu berjalan 10 kali terlepas dari ukuran input adalah O(1), meskipun ada loop yang ada. Pemeriksa suka menyelinap ini.

Algoritma sorting umum dan Big O mereka

Ini adalah topik ujian favorit karena menggabungkan dua spec sekaligus: algoritma sorting dan kompleksitas.

Algoritma	Kasus terbaik	Kasus terburuk
Bubble sort	O(n)	O(n²)
Insertion sort	O(n)	O(n²)
Merge sort	O(n log n)	O(n log n)
Binary search	O(1)	O(log n)
Linear search	O(1)	O(n)

Konsistensi merge sort (kompleksitas sama pada kasus terbaik dan terburuk) layak disebutkan secara eksplisit jika pertanyaan menanyakan mengapa Anda memilihnya daripada bubble sort untuk dataset besar. Kasus terbaik bubble sort O(n) hanya berlaku dengan optimisasi early-exit ketika tidak ada pertukaran yang terjadi dalam satu pass — sebutkan detail itu jika Anda membawanya, karena beberapa badan ujian mengharapkannya.

Di mana siswa kehilangan nilai

Yang terbesar: menulis