Big O, Big Omega, Big Theta ve Neden Önemli?
Algoritma analizi, bir algoritmanın ne kadar zaman ve bellek (alan) kullandığını matematiksel olarak ifade etme bilimidir.
Algoritma analizini anlamak için bilgisayarın temel çalışma prensiplerini bilmek gerekir.
| İşlem | Süre | İnsan Ölçeği* |
|---|---|---|
| CPU'da toplama/çarpma | ~0.3 nanosaniye | 1 saniye |
| L1 Cache okuma | ~1 nanosaniye | 3 saniye |
| RAM okuma | ~100 nanosaniye | 5 dakika |
| SSD okuma | ~100.000 nanosaniye | 4 gün |
| HDD okuma | ~10.000.000 nanosaniye | 1 yıl |
*CPU işlemi 1 saniye olsaydı, diğer işlemler ne kadar sürerdi?
Bir algoritmanın çalışma süresinin, girdi boyutuna (n) göre nasıl değiştiğini gösterir.
Aşağıdaki kodda kaç "temel işlem" yapılıyor?
# n elemanlı bir listede toplam bulma
def toplam_bul(liste):
toplam = 0 # 1 adım (atama)
for x in liste: # n kez döner
toplam += x # n adım (her döngüde 1)
return toplam # 1 adım
# Toplam: 1 + n + 1 = n + 2 adım
# Big O: O(n) (sabitler önemsiz, n önemli)n = 1.000.000 olduğunda:
n + 2 → 1.000.002n² → 1.000.000.000.000 (1 trilyon!)Gördüğünüz gibi, n büyüdükçe sabitler (+2) ve küçük terimler anlamsızlaşır.
Big O, algoritmanın en kötü durumda ne kadar süreceğini gösterir.
"f(n), g(n)'den daha hızlı büyümez"
Girdi boyutu ne olursa olsun, işlem sayısı aynıdır.
Örnekler: Dizide index ile erişim, stack push/pop, hash table ekleme
arr[5] # Her zaman 1 adımHer adımda problem boyutu yarıya iner. n iki katına çıkınca sadece 1 adım eklenir.
Örnekler: Binary search, dengeli BST arama
# Binary Search: 1 milyon elemanda sadece ~20 karşılaştırma!Girdi boyutuyla orantılı. n iki katına çıkarsa, süre de iki katına çıkar.
Örnekler: Lineer arama, dizi toplama, tek döngü
for x in liste: # n kez döner
print(x)Verimli sıralama algoritmalarının sınırı.
Örnekler: Merge sort, Quick sort (ortalama), Heap sort
İç içe iki döngü. n iki katına çıkarsa, süre dört katına çıkar!
Örnekler: Bubble sort, Selection sort, basit matris çarpımı
for i in range(n): # n kez
for j in range(n): # n kez → toplam n×n = n²
print(i, j)n bir artınca süre iki katına çıkar. Pratikte kullanılamaz!
Örnekler: Tüm alt kümeleri bulma, bazı recursive algoritmalar
n = 16 için her karmaşıklığın kaç işlem gerektirdiği:
| Karmaşıklık | n = 16 | n = 256 | n = 1.000 | n = 1.000.000 |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 1 |
| O(log n) | 4 | 8 | 10 | 20 |
| O(n) | 16 | 256 | 1.000 | 1.000.000 |
| O(n log n) | 64 | 2.048 | 10.000 | 20.000.000 |
| O(n²) | 256 | 65.536 | 1.000.000 | 1.000.000.000.000 |
| O(2ⁿ) | 65.536 | 10⁷⁷ | ∞ | ∞ |
Alt Sınır - En İyi Durum
"En azından bu kadar sürer"
Üst Sınır - En Kötü Durum
"En fazla bu kadar sürer"
Sıkı Sınır - Ortalama Durum
"Her zaman bu civarda sürer"
def lineer_ara(liste, hedef):
for i, eleman in enumerate(liste):
if eleman == hedef:
return i
return -1
# En iyi durum: İlk elemanda bulunur → Ω(1)
# En kötü durum: Son elemanda veya yok → O(n)
# Ortalama durum: Ortada bir yerde → Θ(n/2) = Θ(n)Algoritmanın ne kadar ek bellek kullandığını gösterir.
# Örnek 1: O(1) Alan - Sabit bellek
def toplam_bul(liste):
toplam = 0 # Sadece 1 değişken
for x in liste:
toplam += x
return toplam
# Liste ne kadar büyük olursa olsun, sadece 'toplam' değişkeni var
# Örnek 2: O(n) Alan - Yeni liste oluşturma
def kareleri_al(liste):
sonuc = [] # Yeni liste (n eleman tutacak)
for x in liste:
sonuc.append(x ** 2)
return sonuc
# Girdi kadar yer kaplayan yeni liste oluşturuyor
# Test
orijinal = [1, 2, 3, 4, 5]
print(f"Toplam: {toplam_bul(orijinal)}")
print(f"Kareler: {kareleri_al(orijinal)}")Bazen daha fazla bellek kullanarak daha hızlı algoritmalar yazabiliriz (veya tersi).
| Yaklaşım | Zaman | Alan | Açıklama |
|---|---|---|---|
| Hash Table | O(1) | O(n) | Hızlı ama bellek yer |
| Binary Search | O(log n) | O(1) | Az bellek, sıralı veri gerekli |
# Örnek Analiz
# Örnek 1: İç içe döngü → O(n²)
def ornek1(n):
sayac = 0
for i in range(n): # n kez
for j in range(n): # n kez → n × n = n²
sayac += 1
return sayac
# Örnek 2: Ardışık döngüler → O(n) + O(n) = O(n)
def ornek2(n):
for i in range(n): # n kez
print(f"Döngü 1: {i}")
for j in range(n): # n kez
print(f"Döngü 2: {j}") # Toplam: 2n → O(n)
# Örnek 3: Logaritmik → O(log n)
def ornek3(n):
sayac = 0
while n > 1:
n = n // 2 # Her seferinde yarıya böl
sayac += 1
return sayac
# Test
print(f"n=16 için iç içe döngü: {ornek1(16)} işlem")
print(f"n=16 için log: {ornek3(16)} işlem")
print(f"n=1024 için log: {ornek3(1024)} işlem")Bu derste öğreneceğiniz veri yapılarının performans karşılaştırması:
| Veri Yapısı | Erişim | Arama | Ekleme | Silme |
|---|---|---|---|---|
| Array (Dizi) | O(1) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) |
| Queue | O(n) | O(n) | O(1) | O(1) |
| Linked List | O(n) | O(n) | O(1)* | O(1)* |
| BST (Dengeli) | O(log n) | O(log n) | O(log n) | O(log n) |
| Hash Table | - | O(1) | O(1) | O(1) |
* Linked List'te ekleme/silme O(1), ama önce konumu bulmak O(n) gerektirir.