Algoritmalar ve Big-O: arama, sıralama, iki işaretçi, dinamik programlama, BFS/DFS

Neden önemli?

Anadolu Market'in "aynı müşteri, aynı gün, aynı tutar" şüpheli sipariş kontrolü test ortamında 1.000 siparişle bir saniyede çalışıyordu. Canlıya çıkınca günde 2 milyon sipariş geldi ve iş saatlerce sürdü. Kod yanlış değildi; algoritma ölçeklenmiyordu: her siparişi diğer her siparişle karşılaştırıyordu. 1.000 sipariş için 1 milyon karşılaştırma, 2 milyon sipariş için 4 trilyon.

Bu derste algoritmanın maliyetini Big-O ile konuşmayı, klasik arama ve sıralama algoritmalarını ve iş hayatında en çok karşına çıkacak çözüm kalıplarını öğreneceksin. Veri yapılarını bir önceki Veri yapıları dersinde gördün; profil alma ve ölçümü Profil ve optimizasyon, mülakat kalıplarını Mülakat hazırlığı dersinde derinleştireceksin.

Big-O sezgisi

Big-O, girdi büyüdükçe adım sayısının nasıl büyüdüğünü anlatır; saniye değil, büyüme hızıdır. Sabitler ve küçük terimler atılır: 3n + 5 adım O(n)'dir. Bellek için de aynı dil kullanılır: ek bir liste kuran algoritma O(n) bellek (space) kullanır.

Sezgiyi kurmanın en iyi yolu adım saymaktır:

def adim_say(n):
    tek = cift = 0
    for i in range(n):          # tek döngü
        tek += 1
    for i in range(n):          # iç içe döngü
        for j in range(n):
            cift += 1
    return tek, cift

for n in [10, 100, 1000]:
    print(n, adim_say(n))

n on katına çıkınca tek döngü on kat, iç içe döngü yüz kat büyür. Şüpheli sipariş problemindeki çözüm de buradan gelir: siparişleri (müşteri, gün, tutar) anahtarıyla bir sözlükte toplamak tek geçiştir, O(n).

Doğrusal arama ve ikili arama

Doğrusal arama (linear search) baştan sona bakar: O(n). Veri sıralıysa ikili arama (binary search) ortadaki elemana bakar ve aramayı her adımda yarıya indirir: O(log n). 1 milyon elemanda en fazla 20 adım. Python'da hazır hâli bisect modülüdür.

import bisect
fiyatlar = [49, 75, 120, 120, 120, 300, 999]
print(bisect.bisect_left(fiyatlar, 120))    # 120'nin ilk konumu (sola yerleştirme)
print(bisect.bisect_right(fiyatlar, 120))   # son 120'nin bir sağı
print(bisect.bisect_right(fiyatlar, 120) - bisect.bisect_left(fiyatlar, 120), "adet 120 TL")
bisect.insort(fiyatlar, 150)                # sırayı bozmadan ekle
print(fiyatlar)

def var_mi(sirali, x):
    i = bisect.bisect_left(sirali, x)
    return i < len(sirali) and sirali[i] == x
print(var_mi(fiyatlar, 300), var_mi(fiyatlar, 301))

bisect'in en güçlü kullanımı dilim tablolarıdır: vergi dilimi, kargo ücreti, not aralığı, risk skoru. Uzun bir if/elif zinciri yerine sınırları bir listeye koyar, hangi aralıkta olduğunu bisect ile bulursun:

import bisect
SINIRLAR = [1000, 5000, 20000]          # TL
PUAN = ["düşük", "orta", "yüksek", "çok yüksek"]
def risk(tutar):
    return PUAN[bisect.bisect_right(SINIRLAR, tutar)]
for t in [500, 1000, 4999, 5000, 75000]:
    print(t, risk(t))

Sıralama algoritmaları

Python'da her gün sorted kullanırsın; ama klasik algoritmaları bilmek hem mülakatlarda sorulur hem de "neden bazı çözümler yavaş" sorusunu cevaplar. Üç basit algoritma O(n²)'dir:

• Kabarcık (bubble): komşuları karşılaştırıp yer değiştirir; her turda en büyük sona "kabarır".
• Seçmeli (selection): kalanların en küçüğünü bulup başa koyar; az yer değiştirme yapar.
• Eklemeli (insertion): her elemanı solundaki sıralı kısımda yerine kaydırır; neredeyse sıralı veride O(n)'e yaklaşır.

def kabarcik(a):
    a, k = list(a), 0
    for son in range(len(a) - 1, 0, -1):
        degisti = False
        for i in range(son):
            k += 1
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                degisti = True
        if not degisti:              # hiç değişmediyse liste sıralı
            break
    return a, k

def secmeli(a):
    a, k = list(a), 0
    for i in range(len(a)):
        en_kucuk = i
        for j in range(i + 1, len(a)):
            k += 1
            if a[j] < a[en_kucuk]:
                en_kucuk = j
        a[i], a[en_kucuk] = a[en_kucuk], a[i]
    return a, k

veri = [42, 7, 19, 3, 88, 21, 5, 64]
print(kabarcik(veri), secmeli(veri))
print("sıralı girdi:", kabarcik(sorted(veri))[1], "karşılaştırma (kabarcık),", secmeli(sorted(veri))[1], "(seçmeli)")

Sıralı girdide kabarcık erken çıkışla n-1 karşılaştırmada biter; seçmeli ise her durumda n(n-1)/2 karşılaştırma yapar. Aynı Big-O sınıfındaki algoritmalar bile girdiye göre çok farklı davranabilir.

Böl ve fethet (divide and conquer) algoritmaları O(n log n)'e iner. Birleştirme sıralaması (merge sort) listeyi ikiye böler, her yarıyı sıralar ve iki sıralı listeyi tek geçişte birleştirir. Hızlı sıralama (quick sort) bir pivot seçer, küçükleri sola büyükleri sağa ayırır ve her parçayı sıralar.

def birlestirme(a):
    if len(a) <= 1:
        return list(a)
    orta = len(a) // 2
    sol, sag = birlestirme(a[:orta]), birlestirme(a[orta:])
    sonuc, i, j = [], 0, 0
    while i < len(sol) and j < len(sag):
        if sol[i] <= sag[j]:          # <= kararlılığı korur
            sonuc.append(sol[i]); i += 1
        else:
            sonuc.append(sag[j]); j += 1
    return sonuc + sol[i:] + sag[j:]

def hizli(a):
    if len(a) <= 1:
        return list(a)
    pivot = a[len(a) // 2]
    return (hizli([x for x in a if x < pivot]) + [x for x in a if x == pivot]
            + hizli([x for x in a if x > pivot]))

veri = [42, 7, 19, 3, 88, 21, 5, 64, 19]
print(birlestirme(veri))
print(hizli(veri))

Timsort, Python'ın sorted ve list.sort algoritmasıdır: birleştirme ve eklemeli sıralamanın melezidir, verideki hazır sıralı parçaları (run) bulur ve gerçek hayattaki "kısmen sıralı" veride çok hızlıdır. En önemli özelliği kararlı (stable) olmasıdır: anahtarı eşit olan elemanlar orijinal sıralarını korur. Bu sayede çok anahtarlı sıralamayı iki adımda yapabilirsin:

siparisler = [("Ankara", 250), ("İzmir", 975), ("Ankara", 975), ("Bursa", 250), ("İzmir", 120)]
# Hedef: tutara göre azalan, eşit tutarda şehre göre artan
adim1 = sorted(siparisler, key=lambda s: s[0])                 # önce İKİNCİL anahtar
adim2 = sorted(adim1, key=lambda s: s[1], reverse=True)        # sonra birincil
print(adim2)
print(sorted(siparisler, key=lambda s: (-s[1], s[0])) == adim2)   # tek adımlı karşılığı

İki işaretçi ve kayan pencere

İki işaretçi (two pointers) kalıbında sıralı bir dizide iki indeks birbirine doğru ya da aynı yönde ilerler; iç içe döngü gerektiren birçok soru tek geçişe iner. Kayan pencere (sliding window) ise ardışık bir aralığı genişletip daraltarak "en kısa/en uzun ardışık dönem" sorularını O(n) çözer: sağ uç her adımda ilerler, koşul sağlandıkça sol uç daralır.

def hedef_ciro_donemi(gunluk, hedef):
    """Toplamı hedefe ulaşan en kısa ardışık gün sayısı (değerler pozitif)."""
    sol, toplam, en_kisa = 0, 0, None
    for sag, deger in enumerate(gunluk):
        toplam += deger                         # pencereyi sağa genişlet
        while toplam >= hedef:                  # koşul sağlanıyor: soldan daralt
            uzunluk = sag - sol + 1
            en_kisa = uzunluk if en_kisa is None else min(en_kisa, uzunluk)
            toplam -= gunluk[sol]
            sol += 1
    return en_kisa

ciro = [120, 80, 400, 90, 300, 50, 600]
print(hedef_ciro_donemi(ciro, 650), hedef_ciro_donemi(ciro, 5000))

Her eleman pencereye bir kez girer, bir kez çıkar: toplam O(n). Aynı soruyu tüm (başlangıç, bitiş) çiftlerini deneyerek çözmek O(n²) olurdu.

Önek toplamı

"3. günden 10. güne kadar ciro ne?" sorusu günde binlerce kez soruluyorsa her seferinde toplamak O(n)'dir. Önek toplamı (prefix sum) dizisini bir kez kurarsın; sonra her aralık toplamı tek çıkarma işlemidir, O(1).

from itertools import accumulate
ciro = [120, 80, 400, 90, 300, 50, 600]
onek = [0, *accumulate(ciro)]           # onek[i] = ilk i günün toplamı
print(onek)
def aralik(i, j):                        # i..j günleri dahil (0 tabanlı)
    return onek[j + 1] - onek[i]
print(aralik(2, 4), sum(ciro[2:5]))
print(aralik(0, 6) == sum(ciro))

Değerler negatif değilse önek dizisi sıralıdır; "kümülatif ciro ilk hangi gün 1000'i geçti?" sorusunu bisect ile O(log n) cevaplarsın. Bu, iki tekniği birleştirmenin güzel bir örneğidir.

Açgözlü yaklaşım ve dinamik programlama

Açgözlü (greedy) algoritma her adımda o an en iyi görünen seçimi yapar ve geri dönmez. Türk lirası küpürleriyle para üstü vermek için "her seferinde sığan en büyük küpürü ver" doğru sonucu verir. Ama küpürler değişince açgözlü yaklaşım yanılabilir:

def acgozlu(tutar, kupurler):
    sonuc = []
    for k in sorted(kupurler, reverse=True):
        while tutar >= k:
            sonuc.append(k)
            tutar -= k
    return sonuc

print(acgozlu(185, [200, 100, 50, 20, 10, 5, 1]))
print(acgozlu(6, [1, 3, 4]))     # 4+1+1 = 3 adet, ama 3+3 = 2 adet!

def en_az_kupur(tutar, kupurler):
    en_az = [0] + [float("inf")] * tutar        # en_az[t]: t için en az küpür
    for t in range(1, tutar + 1):
        for k in kupurler:
            if k <= t and en_az[t - k] + 1 < en_az[t]:
                en_az[t] = en_az[t - k] + 1
    return en_az[tutar]
print(en_az_kupur(6, [1, 3, 4]))

İkinci fonksiyon dinamik programlamadır (dynamic programming, DP): büyük problemi örtüşen küçük alt problemlere böler, her alt problemi bir kez çözüp tabloya yazar. DP'ye iki yoldan gidilir: yukarıdan aşağı özyineleme (recursion) + önbellek (memoization, functools.cache) ya da aşağıdan yukarı tablo doldurma (tabulation).

Klasik ısınma problemi merdiven: n basamaklı merdiveni birer ya da ikişer basamak çıkarak kaç farklı yolla çıkarsın? Son adım ya 1 ya 2 basamaktır, öyleyse yol(n) = yol(n-1) + yol(n-2).

from functools import cache
cagri = 0
def saf(n):
    global cagri
    cagri += 1
    return 1 if n <= 1 else saf(n - 1) + saf(n - 2)

@cache
def hatirlayan(n):
    return 1 if n <= 1 else hatirlayan(n - 1) + hatirlayan(n - 2)

def tablo(n):
    once, simdi = 1, 1                  # yol(0), yol(1)
    for _ in range(n - 1):
        once, simdi = simdi, once + simdi
    return simdi

print(saf(25), "çağrı sayısı:", cagri)
print(hatirlayan(25), tablo(25), tablo(90))

Saf özyineleme aynı alt problemleri tekrar tekrar çözer ve üstel büyür; önbellekli ve tablolu sürümler O(n)'dir. Tablolu sürüm yalnızca son iki değeri tuttuğu için O(1) bellek kullanır.

İş hayatındaki DP örneği: en uzun ortak alt dizi (longest common subsequence, LCS). İki metindeki karakterlerin sırası bozulmadan seçilebilecek en uzun ortak dizi; diff araçları, yazım düzeltme ve kayıt eşleştirme bunun üstüne kurulur.

def lcs_uzunluk(a, b):
    T = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                T[i][j] = T[i - 1][j - 1] + 1          # karakterler eşleşti
            else:
                T[i][j] = max(T[i - 1][j], T[i][j - 1])  # birini atla
    return T[-1][-1]
print(lcs_uzunluk("ATATÜRK CAD", "ATATURK CADDESI"))
print(lcs_uzunluk("KIZILAY", "KIZILCAHAMAM"))

BFS ve DFS: grafı gezmek

Grafı gezmenin iki temel yolu vardır. BFS (genişlik öncelikli arama, breadth-first search) bir kuyrukla katman katman ilerler; ağırlıksız grafta en kısa yolu bulur. DFS (derinlik öncelikli arama, depth-first search) bir yığınla (ya da özyinelemeyle) bir dalın sonuna kadar gider; bağlı bileşenleri, döngüleri ve erişilebilirliği bulmakta kullanılır. İkisi de O(düğüm + kenar) çalışır.

from collections import deque
yollar = {"Gebze": ["İstanbul", "Bursa", "Kocaeli"], "İstanbul": ["Gebze", "Tekirdağ"],
          "Bursa": ["Gebze", "İzmir", "Eskişehir"], "Eskişehir": ["Bursa", "Ankara"],
          "Ankara": ["Eskişehir"], "İzmir": ["Bursa"], "Kocaeli": ["Gebze"], "Tekirdağ": ["İstanbul"]}

def bfs_yol(graf, bas, hedef):
    onceki = {bas: None}
    kuyruk = deque([bas])
    while kuyruk:
        d = kuyruk.popleft()
        if d == hedef:
            yol = []
            while d is not None:
                yol.append(d); d = onceki[d]
            return yol[::-1]
        for k in graf.get(d, []):
            if k not in onceki:          # ziyaret edildi mi? (set gibi O(1))
                onceki[k] = d
                kuyruk.append(k)
    return None

def dfs_erisilen(graf, bas):
    gorulen, yigin = set(), [bas]
    while yigin:
        d = yigin.pop()
        if d not in gorulen:
            gorulen.add(d)
            yigin.extend(graf.get(d, []))
    return gorulen

print(" -> ".join(bfs_yol(yollar, "Tekirdağ", "Ankara")))
print(len(dfs_erisilen(yollar, "İzmir")), "depoya ulaşılabilir")

BFS ile DFS arasındaki tek fark kuyruk mu yığın mı kullandığındır; veri yapısı seçimi algoritmanın davranışını belirler. Ağırlıklı grafta (yolların km'si farklıysa) en kısa yol için BFS yerine heapq kullanan Dijkstra algoritması gerekir.