Big O Gösterimi: A-Level Bilgisayar Bilimleri Aslında Ne Bekliyor

Big O gösterimi her büyük A-level bilgisayar bilimleri müfredat standardında (AQA, OCR, Edexcel) karşımıza çıkıyor ve birçok öğrenciyi matematikten dolayı değil, aksine hiç gerçek kodla bağlantılı olarak görmediği için zorluyor. Bu, bilmeniz gereken şeyin ve sınav sorularına boş konuşmadan nasıl cevap vereceğinizin pratik bir incelemesidir.

Big O aslında ne ölçer

Big O, bir algoritmanın çalışma süresi (veya bellek kullanımı) ile giriş boyutunun (genellikle n olarak adlandırılır) büyümesinin ilişkisini tanımlar. Saniye cinsinden bir kronometre ölçümü değildir. Algoritmaları donanımdan bağımsız olarak karşılaştırabilmek için büyüme hızını tanımlamanın bir yoludur.

O(n) yazarken şunu söylüyorsunuz: girişi iki katına çıkarırsam, işin miktarı kabaca iki katına çıkar. O(n²) girişi iki katına çıkarmanın işin miktarını kabaca dört katına çıkardığı anlamına gelir. Sınav soruluları tam işlem sayılarını değil, bu ilişkiyi belirlemenizi isterler.

Soğuk bilmeniz gereken karmaşıklıklar

A-level için, bunlar tekrar tekrar ortaya çıkanlardır:

• O(1) – sabit zaman. Bir dizi öğesine indeksle erişim: arr[5]. Dizinin ne kadar büyük olması fark etmez.
• O(log n) – logaritmik. Sıralı bir listede ikili arama. Her adım kalan arama alanını yarıya indirir.
• O(n) – doğrusal. Bir list üzerinde tek bir döngü, örneğin her öğeyi bir kez kontrol eden doğrusal arama.
• O(n log n) – doğrusaljitmik. Merge sort ve quicksort (ortalama durum) buraya girer.
• O(n²) – ikinci derece. Aynı veriler üzerinde iç içe döngüler, tam olarak bubble sort, insertion sort ve selection sort'un yaptığı şey.
• O(2ⁿ) – üstel. Memoization olmadan naif yinelemeli Fibonacci. Hızla kötüleşir.

Sözde koda bakıp bunlardan hangisinin olduğunu bir bakışta söyleyebilmelisiniz, çünkü sınanılan çoğunlukla budur.

Karmaşıklık için kodu okumak

Her zaman işe yarayan yöntem: döngüleri sayın ve n ile nasıl ilişkili olduklarını görün.

# O(n) - bir döngü, bir geçiş
for i in range(n):
    print(i)

# O(n^2) - iç içe döngü, her ikisi de n'ye bağlı
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - arama alanı her iterasyonda yarıya iner
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

İç döngünün aralığı n'ye bağlı olan iç içe döngü yine O(n²)'dir, biraz farklı görünse de (for j in range(i) yerine for j in range(n) — bu yine ikinci derecedir, sadece sabit bir faktör farkıyla).

n'ye hiç bağlı olmayan döngülere dikkat edin. Giriş boyutundan bağımsız olarak her zaman 10 kez çalışan bir döngü O(1)'dir, döngü mevcut olsa da. Sınav soruluları bunu gizlice sokmayı severler.

Yaygın sıralama algoritmaları ve Big O'ları

Bu, iki müfredat standardını birden birleştirdiği için (sıralama algoritmaları ve karmaşıklık) sevilen bir sınav konusudur.

Algoritma	En iyi durum	En kötü durum
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)

Merge sort'un tutarlılığı (aynı karmaşıklık en iyi ve en kötü durum) bir soru neden bubble sort'u büyük veri setleri için seçeceğinizi soruyorsa açıkça belirtmeye değer. Bubble sort'un O(n) en iyi durumu sadece hiçbir takas olmadığında erken çıkış optimizasyonuyla uygulanır — bunu ortaya koyarsanız bahsetmeye değer, çünkü bazı sınav kurulları bunu bekler.

Öğrencilerin puan kaybettiği yerler

En büyüğü: yazma