Doğrusal Arama

Çözümleme araçları hazır; bu konu onları ilk kez bir algoritma ailesine uygular. Arama ve sıralama, aynı problemin farklı maliyetlerdeki çözümlerini yan yana koymaya elverişli olduğu için bu iş için uygun bir zemindir.

En basit aramayla başlanır: elemanları baştan sona gezmek.

Algoritma ve Doğruluğu

Doğrusal arama, diziyi baştan sona tarar ve aranan değeri bulduğu ilk konumu döndürür.

def dogrusal_arama(dizi: list[int], hedef: int) -> int:
    """Hedefin ilk konumu; yoksa -1.

    Değişmez: her turun başında, 0..i-1 aralığında hedef yoktur.
    Sonlanma: kalan eleman sayısı her turda bir azalır.
    """
    for i in range(len(dizi)):
        if dizi[i] == hedef:
            return i
    return -1


olcumler = [5, 2, 9, 1, 5, 6]
print(dogrusal_arama(olcumler, 9))     # 2
print(dogrusal_arama(olcumler, 5))     # 0   — ilk eşleşme
print(dogrusal_arama(olcumler, 7))     # -1

Doğruluğu belgedeki iki cümle verir. Döngü değişmezi, döngü bittiğinde “0..n-1 aralığında hedef yoktur” hâline gelir; bu da -1 dönüşünü gerekçelendirir. Azalan büyüklük, sonlanma güvencesidir.

İki tasarım kararı örtük olarak alınmıştır: eşit değerler varsa ilk konum döndürülür ve bulunamama, geçerli bir dizin olamayacak bir değerle bildirilir.

Üç Durumun Maliyeti

Ölçüt karşılaştırma sayısıdır.

En iyi durum: Hedef ilk elemandır; 1 karşılaştırma, $O(1)$.

En kötü durum: Hedef son elemandır veya hiç yoktur; $n$ karşılaştırma, $O(n)$.

Ortalama durum: Hedefin dizide bulunduğu ve her konumun eşit olasılıklı olduğu varsayılırsa, beklenen karşılaştırma sayısı

$$\frac{1 + 2 + \dots + n}{n} = \frac{n+1}{2}$$

olur; bu da $O(n)$’dir. Başarısız aramada her zaman $n$ karşılaştırma yapılır.

def karsilastirma_sayisi(dizi: list[int], hedef: int) -> int:
    for i in range(len(dizi)):
        if dizi[i] == hedef:
            return i + 1
    return len(dizi)


dizi = list(range(100))
toplam = sum(karsilastirma_sayisi(dizi, h) for h in dizi)
print(toplam / len(dizi))                    # 50.5   — (n+1)/2
print(karsilastirma_sayisi(dizi, -1))        # 100    — başarısız arama

Ortalama, en kötü durumun yaklaşık yarısıdır. Sabit çarpan farkı asimptotik sınıfı değiştirmez: iki durum da doğrusaldır. Bu, ortalama durum çözümlemesinin ne zaman anlamlı olduğunu gösterir — sınıfı değil, sabiti belirler.

Nöbetçi Değişkeni

Döngü her turda iki sınama yapar: dizin sınırı aşıldı mı, eleman hedefe eşit mi. Hedef dizinin sonuna geçici olarak eklenirse, sınır sınaması gereksizleşir; arama en geç o elemanda durur.

def nobetci_ile_arama(dizi: list[int], hedef: int) -> int:
    dizi.append(hedef)                 # nöbetçi
    i = 0
    while dizi[i] != hedef:
        i += 1
    dizi.pop()
    return i if i < len(dizi) else -1


d = [5, 2, 9, 1, 5, 6]
print(nobetci_ile_arama(d, 9), nobetci_ile_arama(d, 7), d)   # 2 -1 [5, 2, 9, 1, 5, 6]

Kazanç sabit çarpandadır; sınıf yine $O(n)$’dir. Yöntemin bedeli, diziyi geçici olarak değiştirmesidir — paylaşılan veride veya çok iş parçacıklı bir ortamda kullanılamaz.

Bu, kursun tekrar eden bir dersidir: sabit iyileştirmeler gerçektir ama sınıfı değiştiren bir fikrin yerini tutmaz.

Neden Daha İyisi Yapılamaz

Sırasız bir dizide aramanın maliyeti düşürülemez ve bunun gerekçesi bir karşı oyuncu akıl yürütmesidir.

Bir algoritmanın $n$ elemanın hepsine bakmadığını varsayalım. Bakmadığı en az bir konum vardır. Karşı oyuncu, algoritma “bulunamadı” dediğinde o konuma hedefi yerleştirir; algoritmanın gözlemleri değişmediği için yanıtı da değişmez, ama yanıt artık yanlıştır.

Öyleyse doğru çalışan her algoritma, en kötü durumda tüm elemanlara bakmak zorundadır: sırasız veride arama $\Omega(n)$’dir. Doğrusal arama bu sınıra ulaştığı için, sıra varsayımı olmadan eniyidir.

Sınırdan kaçmanın tek yolu varsayımı değiştirmektir: veriyi sıralı tutmak veya bir dizin yapısı kurmak. Sonraki ders birinci yolu, Veri Yapıları kursundaki karma tablosu ikinci yolu izler.

Erişim Dağılımı ve Sıralamanın Etkisi

Ortalama durum hesabı, her elemanın eşit olasılıkla arandığını varsayıyordu. Gerçek erişimler çoğu zaman eşit dağılmaz: birkaç kayıt sık, geri kalanı seyrek aranır.

Beklenen karşılaştırma sayısı, $i$ numaralı elemanın aranma olasılığı $p_i$ iken

$$\sum_{i=1}^{n} i \cdot p_i$$

olur. İfade, elemanlar azalan olasılık sırasına dizildiğinde en küçük değerini alır. Yani dizinin sırası maliyeti belirler ve en iyi statik düzen, sıklığa göre sıralamadır.

def beklenen_maliyet(olasiliklar: list[float]) -> float:
    return sum((i + 1) * p for i, p in enumerate(olasiliklar))


print(round(beklenen_maliyet([0.1, 0.2, 0.7]), 2))      # 2.6   — kötü düzen
print(round(beklenen_maliyet([0.7, 0.2, 0.1]), 2))      # 1.4   — sıklığa göre

Sıklıklar önceden bilinmiyorsa, listeyi çalışma anında düzenleyen sezgiler kullanılır: bulunan eleman başa taşınır ya da bir sıra öne alınır. Bunlar en kötü durumu değiştirmez — sınıf yine $O(n)$’dir — ancak eğik dağılımlarda ortalamayı belirgin biçimde düşürür.

Tek Geçişte Birden Çok Bilgi

Doğrusal tarama yalnızca eşleşme aramaz; aynı geçişte birkaç büyüklük birden toplanabilir. En küçük ile en büyüğü ayrı ayrı aramak $2n$ karşılaştırma ister; elemanlar ikişer ikişer işlenirse maliyet düşer.

def en_kucuk_ve_en_buyuk(dizi: list[int]) -> tuple[int, int, int]:
    """(en küçük, en büyük, karşılaştırma sayısı) döndürür."""
    n = len(dizi)
    if n % 2 == 0:
        kucuk, buyuk = min(dizi[0], dizi[1]), max(dizi[0], dizi[1])
        i, sayac = 2, 1
    else:
        kucuk = buyuk = dizi[0]
        i, sayac = 1, 0

    while i < n - 1:
        a, b = dizi[i], dizi[i + 1]
        if a > b:
            a, b = b, a
        sayac += 3                      # çift içi + iki uçla karşılaştırma
        kucuk = min(kucuk, a)
        buyuk = max(buyuk, b)
        i += 2
    return kucuk, buyuk, sayac


print(en_kucuk_ve_en_buyuk([5, 2, 9, 1, 5, 6]))          # (1, 9, 7)
print(en_kucuk_ve_en_buyuk(list(range(100))))            # (0, 99, 148)

Yüz eleman için 148 karşılaştırma yapılır; ayrı ayrı arama 198 isterdi. Genel formül $3n/2 - 2$’dir ve bu, iki uç için bilinen alt sınırdır.

Sınıf yine $O(n)$’dir. Kazanç, veri diskten veya ağdan geliyorsa ve her geçiş pahalıysa önem kazanır: tek geçişte toplanabilecek her bilgi, ikinci bir geçişten ucuzdur.

Özet

• Doğrusal arama sırasız veride çalışır; doğruluğu döngü değişmezi ve azalan büyüklükle gerekçelendirilir.
• En iyi durum sabit, en kötü durum doğrusaldır; başarılı aramanın beklenen maliyeti $(n+1)/2$ karşılaştırmadır.
• Nöbetçi değişkeni sınır sınamasını kaldırır; kazanç sabit çarpandadır, sınıf değişmez.
• Karşı oyuncu akıl yürütmesi, sırasız veride aramanın $\Omega(n)$ olduğunu gösterir; doğrusal arama bu sınıra ulaşır.
• Erişim olasılıkları eşit değilse, elemanları azalan sıklıkla dizmek beklenen maliyeti düşürür.
• Tek geçişte birden çok büyüklük toplamak, geçiş sayısını ve toplam karşılaştırmayı düşürür.

Sonraki Adım

Doğrusal alt sınırdan kaçmanın yolu, veri üzerinde bir varsayım kurmaktır. Veri sıralıysa her karşılaştırma yalnızca bir elemanı değil, elemanların yarısını eler. Sonraki ders bu fikri — ikili aramayı — ve doğru yazılması şaşırtıcı derecede zor olan sınır koşullarını ele alacak.