Neden Bazı Algoritmalar Daha Hızlıdır?
Program A: 1 milyon sayıyı 0.01 saniyede toplar
Program B: 1 milyon sayıyı 12 dakikada toplar
Her ikisi de doğru sonuç veriyor. Fark nedir? → ALGORİTMA!
Algoritma analizi, bir algoritmanın ne kadar hızlı ve ne kadar bellek kullandığını ölçer.
Big O, algoritmanın giriş boyutu (n) büyüdükçe ne kadar yavaşladığını gösterir.
Senaryo: n kitap var, belirli bir kitabı bulacaksın
Algoritmaları performanslarına göre en hızlıdan en yavaşa doğru inceleyelim:
Tanım: Girdi boyutu (n) ne olursa olsun, algoritma her zaman aynı sayıda işlem yapar.
Örnek: Dizinin ilk elemanını okumak - n=10 da 1 işlem, n=1,000,000 da yine 1 işlem!
Performans: ⚡⚡⚡ En hızlı! Gerçek dünyada: hash table lookup, array indexing
# O(1) - Girdi boyutundan bağımsız
def get_first(arr):
"""İlk elemanı döndür - her zaman 1 işlem"""
return arr[0]
# Test
small = [1, 2, 3]
large = list(range(1000000)) # 1 milyon eleman
print(f"3 elemanlı dizi: {get_first(small)}")
print(f"1M elemanlı dizi: {get_first(large)}")
print("\n✅ Her ikisi de aynı hızda!")
print("n = 10 → 1 işlem")
print("n = 1,000,000 → 1 işlem (aynı!)")Tanım: Her adımda problem boyutu yarıya iner. n 1000x artarsa, sadece ~10 adım daha eklenir!
Örnek: Binary search (sıralı dizide arama), ağaçlarda arama. Her adımda yarısını at.
Performans: ⚡⚡ Çok hızlı! Milyonlarca elemanda bile 20-30 adım. Gerçek dünyada: database indexing, binary search
# O(log n) - Binary Search: Sıralı listede arama
def binary_search(liste, aranan):
"""Sıralı listede bir sayıyı bul
Her adımda listenin yarısını ele"""
sol = 0
sag = len(liste) - 1
adim = 0
while sol <= sag:
adim += 1
orta = (sol + sag) // 2
if liste[orta] == aranan:
return adim # Bulduk!
elif liste[orta] < aranan:
sol = orta + 1 # Sağ yarıya bak
else:
sag = orta - 1 # Sol yarıya bak
return adim # Bulunamadı
# Test: Farklı boyutlarda listeler
print("=== Binary Search - O(log n) ===\n")
for n in [10, 100, 1000, 1000000]:
liste = list(range(n)) # [0, 1, 2, ..., n-1]
aranan = n - 1 # En son elemanı ara (en kötü durum)
adim = binary_search(liste, aranan)
print(f"n = {n:>7,} elemanlı listede → {adim:>2} adımda bulundu")
print("\n✅ n 10 kat arttı → sadece ~3 adım eklendi!")
print("✅ 1 milyon elemanda bile sadece 20 adım!")Tanım: İşlem sayısı, girdi boyutuyla doğru orantılı artar. n iki katına çıkarsa, süre de iki katına çıkar.
Örnek: Bir dizinin toplamını hesaplamak - her elemanı bir kez ziyaret etmek gerekir.
Performans: ⚡ İyi! Çoğu basit döngü. Gerçek dünyada: array search, list iteration
# O(n) - Her elemanı bir kez işle
def calculate_sum(arr):
"""Toplamı hesapla - n işlem"""
total = 0
for num in arr: # n kez döner
total += num
return total
# Test
data1 = [1, 2, 3, 4, 5] # 5 eleman
data2 = list(range(100)) # 100 eleman
print(f"5 eleman: toplam = {calculate_sum(data1)}, işlem = 5")
print(f"100 eleman: toplam = {calculate_sum(data2)}, işlem = 100")
print("\n✅ n = 5 → 5 işlem")
print("✅ n = 100 → 100 işlem")
print("✅ n = 1000 → 1000 işlem")Tanım: Her eleman için logaritmik bir işlem yapılır. O(n)'den yavaş ama O(n²)'den çok daha hızlı!
Örnek: Verimli sıralama algoritmaları (merge sort, heap sort, quick sort), her eleman için binary search
Performans: ✅✅ Çok iyi! Büyük verilerde bile pratik. Gerçek dünyada: efficient sorting, divide-and-conquer algoritmaları
import random
# Python'un sort() fonksiyonu O(n log n) kullanır
# Basit örnek: Sıralama işlem sayısını göster
def siralama_karsilastir(n):
"""O(n²) vs O(n log n) karşılaştırması"""
liste = list(range(n))
random.shuffle(liste) # Karıştır
# Kötü yöntem: Her eleman için tüm listeyi tara (O(n²))
kotu_islem = n * n
# İyi yöntem: Merge Sort / Quick Sort (O(n log n))
import math
iyi_islem = int(n * math.log2(n))
return kotu_islem, iyi_islem
# Test
print("=== Sıralama Karmaşıklığı ===\n")
print("Bubble Sort (O(n²)) vs Python sort (O(n log n))\n")
for n in [100, 1000, 10000]:
kotu, iyi = siralama_karsilastir(n)
kat = kotu // iyi
print(f"n = {n:,} eleman:")
print(f" Bubble Sort: {kotu:>12,} karşılaştırma")
print(f" Python sort: {iyi:>12,} karşılaştırma")
print(f" → Python {kat}x daha hızlı!\n")
print("💡 Bu yüzden Python'da sort() kullanın!")
print(" Kendi sıralamanızı yazmayın.")Tanım: İşlem sayısı, girdi boyutunun karesiyle artar. n 10x artarsa, süre 100x artar!
Örnek: İç içe döngüler - her eleman için tüm elemanları işle (bubble sort, tüm ikilileri karşılaştır)
Performans: 🐌 Yavaş! Küçük veriler için sorun yok ama büyük veri için kaçının. Gerçek dünyada: naive sorting, matrix multiplication
# O(n²) - İç içe döngüler
def count_pairs(arr):
"""Tüm ikilileri say - n² işlem"""
count = 0
for i in arr: # n kez
for j in arr: # n kez (her i için)
count += 1
return count
# Test
data = [1, 2, 3, 4]
pairs = count_pairs(data)
print(f"Dizi: {data} (n = {len(data)})")
print(f"İşlem sayısı: {pairs}")
print(f"Formül: n² = {len(data)}² = {pairs}")
print("\n⚠️ n = 10 → 100 işlem")
print("⚠️ n = 100 → 10,000 işlem")
print("⚠️ n = 1000 → 1,000,000 işlem!")
print("\n→ n 10x artınca, süre 100x artar!")Tanım: İşlem sayısı üstel olarak patlar! Her n artışında süre 2x katlanır. n=30'dan sonra kullanılamaz!
Örnek: Naive recursive Fibonacci, tüm alt kümeleri hesaplama, brute-force kombinasyonlar
Performans: 🚫 Çok çok yavaş! n=50 için evrenin yaşından uzun sürer. Gerçek dünyada: kaçınılmalı, optimizasyon şart!
# O(2ⁿ) - ÇOK YAVAŞ! Her çağrı 2 çağrı yapar
def fibonacci_recursive(n):
"""Fibonacci - Naive recursive yaklaşım
Her çağrı 2 alt çağrı yapar → üstel büyüme!"""
if n <= 1:
return n
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)
# Test - KÜçÜK değerlerle!
print("=== O(2ⁿ) - Üstel Karmaşıklık ===\n")
print("⚠️ DİKKAT: n > 35 için çok yavaş!\n")
for n in [5, 10, 15, 20]:
result = fibonacci_recursive(n)
operations = 2**n
print(f"fib({n:>2}) = {result:>6,} → ~{operations:>10,} işlem")
print("\n⚠️ n = 30 → ~1 milyar işlem (birkaç saniye)")
print("⚠️ n = 40 → ~1 trilyon işlem (günler!)")
print("⚠️ n = 50 → Evrenin ömründen uzun sürer!")
print("\n💡 Çözüm: Dynamic Programming (ileride göreceğiz) → O(n)")Kısa cevap: Big O notasyonunda önemsiz!
Uzun cevap: Logaritma değişim formülü:
Yani log₁₀(n) = sabit × log₂(n)
Big O'da sabit katsayılar göz ardı edilir → Her ikisi de O(log n)
import math
print("=== Logaritma Tabanı Karşılaştırması ===\n")
print(f"{'n':>10} | {'log₂(n)':>10} | {'log₁₀(n)':>10} | {'Oran':>10}")
print("-" * 50)
for n in [10, 100, 1000, 10000, 1000000]:
log2_n = math.log2(n)
log10_n = math.log10(n)
ratio = log2_n / log10_n
print(f"{n:>10,} | {log2_n:>10.2f} | {log10_n:>10.2f} | {ratio:>10.2f}")
print("\n💡 Oran hep ~3.32 (log₂(10))")
print("✅ İkisi de O(log n) - aynı karmaşıklık sınıfı!")
print("\n=== Pratik Önemi ===")
print("Binary search: log₂(1M) ≈ 20 adım")
print("Base-10 search: log₁₀(1M) = 6 adım")
print("→ Sabit farkla (3.32x), Big O'da aynı!")
print("\n⚠️ Asimptotik analiz: n → ∞ için davranış")
print(" Sabit farklar kaybolur!")Merge sort ister log₂(n), ister log₁₀(n) kullanın:
→ Logaritma tabanı Big O notasyonunda önemsiz!
Y ekseni görünümünü ayarlayın:
Çoğu insan algoritma hızının önemini küçük verilerle test ederken fark edemez. Asıl fark, kodunuz milyonlarca kez çalıştırıldığında ya da milyarlarca veriyle karşılaştığında ortaya çıkar!
2006'da Netflix, film öneri algoritmasını %10 iyileştiren kişiye 1 milyon dolar ödül vaat etti.
Neden? Çünkü Netflix'in öneri sistemi günde milyarlarca kez çalışıyor. %10'luk bir doğruluk iyileştirmesi:
→ Kazanan takım: Matrix factorization + ensemble yöntemleri kullandı
Not: Bu yarışma algoritma hızından çok doğruluğu arttırmakla ilgiliydi, ama yine de makine öğrenmesi modellerinin verimliliği kritikti.
Google, arama sonuçlarını 0.5 saniye yavaşlatınca trafiğin %20 düştüğünü keşfetti.
Gerçek: Google milyarlarca web sayfasını indeksler
Kullanılan: Inverted index + PageRank (graf algoritması)
Karmaşıklık: Her arama ~O(k log n) - k: arama terimleri, n: toplam sayfa
Eğer kötü algoritma kullansaydı:
Linear search (O(n)): Milyarlarca sayfayı teker teker tara → Saatler sürer
Akıllı indeksleme: Önceden işlenmiş index → Milisaniyeler
→ Veri yapıları (hash table, B-tree) + akıllı önbellek = Hız
İnsan genomunu analiz etmek için DNA dizilerini hizalama gerekiyor.
Problem: 3 milyar baz çiftini referans genoma eşleştir
Naive yöntem: Her parçayı tüm genomda ara → Aylar sürer
BWA (Burrows-Wheeler Aligner): Özel indeksleme → Saatler
Kullanılan teknikler:
→ Fark: İşe yaramaz vs gerçekten kullanılabilir = Tedavi mümkün oluyor!
Facebook (Meta) her gün 3 milyar kullanıcıya kişiselleştirilmiş feed gösteriyor.
Her kullanıcı: Günde ~100 post öneriyor
Toplam: 300 milyar post sıralaması/gün
%1 algoritma iyileştirmesi: 3 milyar daha az işlem/gün
Sonuç:
→ %1 iyileştirme bile gezegeni kurtarmaya yardımcı olabilir!
"Benim projemde sadece 100 kullanıcı var, neden önemli?" diye düşünebilirsiniz. Ama:
"Scalability baştan düşünülmez, sonradan çözülemez!"
Amazon: 100ms yavaşlama = %1 satış kaybı
Daha verimli kod = Daha az sunucu = Daha az karbon
Hızlı uygulama = Mutlu kullanıcı = Daha fazla kullanım
🎯 Ana Mesaj:
Doğru algoritma seçimi hayat kurtarır, milyarlarca dolar tasarruf sağlar ve imkansızı mümkün kılar!