Algoritma Nedir

Veri Yapıları kursu, verinin nasıl düzenlendiğini ve bu düzenin maliyeti nasıl belirlediğini kurdu. Maliyet ifadeleri — $O(1)$, $O(\log n)$, $O(n)$ — kullanıldı ama tanımlanmadı; yalnızca “veri büyüdükçe maliyetin hangi hızla arttığı” biçiminde sezgisel olarak anlatıldı.

Bu kurs o boşluğu kapatır ve soruyu tersine çevirir: veri değil çözüm incelenir. Aynı problemin farklı çözümleri nasıl karşılaştırılır ve karşılaştırma neye göre yapılır?

Algoritmanın Ölçütleri

Algoritma, bir problemi çözen sonlu adımlar dizisidir. Tanım bu kadar kısa olsa da, bir yöntemin algoritma sayılması için beş ölçüt aranır:

Girdi. Sıfır veya daha çok, iyi tanımlanmış girdi alır.

Çıktı. En az bir çıktı üretir ve bu çıktı girdiyle ilişkilidir.

Belirlilik. Her adım tek anlamlıdır; aynı girdi aynı adımları aynı sırayla yürütür. Programlama Temelleri kursundaki belirlilik tartışması buraya bağlanır.

Sonluluk. Her geçerli girdi için sonlu adımda durur. Sonsuz döngüye giren bir yöntem algoritma değildir.

Etkinlik. Her adım, sonlu sürede ve tanımlı araçlarla uygulanabilir olmalıdır. “Doğru yanıtı bul” bir adım değildir; “diziyi baştan sona tara” adımdır.

Beş ölçüt, gündelik dilde “algoritma” denen her şeyi kapsamaz. Rastgeleleştirilmiş yöntemler belirlilik ölçütünü gevşetir; yaklaşık yöntemler çıktının kesinliğini gevşetir. Bu gevşetmeler, ilgili yerlerde açıkça belirtilir.

Problem, Örnek ve Program

Üç kavram sık karıştırılır ve ayrımları kursun geri kalanında varsayılır.

Problem, girdilerle kabul edilebilir çıktılar arasındaki ilişkinin belirtimidir: “girdi, tam sayılardan oluşan bir dizidir; çıktı, aynı elemanların azalmayan sırada dizilmiş hâlidir.” Belirtim bir yöntem söylemez, yalnızca neyin doğru sayılacağını söyler.

Örnek (instance), problemin tek bir girdisidir: [5, 2, 9] dizisi bir örnektir. Bir algoritma, tek bir örneği değil tüm örnekleri çözmelidir; belirli bir girdide doğru yanıt vermek yeterli değildir.

Program, bir algoritmanın belirli bir dilde, belirli bir makine için yazılmış gerçekleştirimidir. Aynı algoritmanın sayısız programı olabilir; hepsi aynı adımları izlediği sürece aynı algoritmadır.

Bu ayrım, doğruluğun neye göre ölçüldüğünü belirler: bir algoritma programa göre değil, problem belirtimine göre doğrudur. Bu nedenle algoritmalar genellikle sözde kodla yazılır — dil ayrıntıları belirtimle ilgisizdir.

Doğruluk İki Parçalıdır

Bir algoritmanın doğru olduğunu söylemek iki ayrı iddiada bulunmaktır:

Kısmi doğruluk: Algoritma durursa, sonuç doğrudur.

Sonlanma: Algoritma her geçerli girdi için durur.

İkisi birlikte tam doğruluk verir. Ayrım, ispatların da iki ayrı parçaya bölünmesini sağlar ve bu bölme pratikte işe yarar — biri sağlanıp diğeri sağlanmayan yöntemler vardır.

Kısmi doğruluğun standart aracı, Programlama Temelleri kursunda tanıtılan döngü değişmezidir: döngüye girmeden önce doğru, her tur korunuyor ve döngü bittiğinde istenen sonucu veriyorsa, kısmi doğruluk kanıtlanmıştır.

Sonlanmanın standart aracı ise azalan bir büyüklüktür: her turda kesin olarak azalan ve alttan sınırlı bir değer bulunursa, döngü sonsuza kadar süremez.

def en_buyugu_bul(olcumler: list[int]) -> int:
    """En büyük ölçümü döndürür. Liste boş olmamalıdır.

    Değişmez: her turun başında `en_buyuk`, o ana kadar gezilen
    elemanların en büyüğüdür.
    Sonlanma: kalan eleman sayısı her turda bir azalır.
    """
    en_buyuk = olcumler[0]
    for olcum in olcumler:
        if olcum > en_buyuk:
            en_buyuk = olcum
    return en_buyuk


print(en_buyugu_bul([12, 18, 7, 25, 14]))     # 25

Belgedeki iki satır süs değildir: biri kısmi doğruluğun, diğeri sonlanmanın gerekçesidir. Bir algoritmanın doğru olduğunu göstermek, bu iki cümleyi yazabilmektir.

Aynı Problem, Farklı Algoritmalar

Bir problemin birden çok çözümü olabilir ve çözümler yalnızca hızda değil, yapıda farklılaşır.

def toplam_dongu(n: int) -> int:
    """1'den n'e kadar sayıların toplamı; her sayı ayrı ayrı eklenir."""
    toplam = 0
    for i in range(1, n + 1):
        toplam += i
    return toplam


def toplam_formul(n: int) -> int:
    """Aynı toplam; kapalı formülle tek adımda."""
    return n * (n + 1) // 2


print(toplam_dongu(100), toplam_formul(100))          # 5050 5050
print(toplam_dongu(1_000_000) == toplam_formul(1_000_000))    # True

İki işlev aynı sonucu verir. Birincisi $n$ toplama yapar; ikincisi bir çarpma, bir toplama ve bir bölme yapar — girdi ne olursa olsun.

Fark, bir eniyileme ayrıntısı değildir: birinci çözümün maliyeti girdiyle büyür, ikincisi büyümez. Bir milyon için birincisi bir milyon işlem, ikincisi üç işlem yapar.

Bu, kursun temel sorusunu somutlaştırır: iki çözüm arasındaki farkı nasıl ölçeriz?

Süre Ölçmek Neden Yetmez

Akla ilk gelen ölçüt, çalışma süresidir. Ancak süre üç etkene birden bağlıdır ve bunların hiçbiri algoritmanın kendisine ait değildir.

Donanım. Aynı program farklı işlemcilerde farklı sürer; Bilgisayarlar Nasıl Çalışır kursundaki bellek hiyerarşisi bu farkın kaynaklarından biriydi.

Gerçekleştirim. Dil, derleyici ve çalışma zamanı seçimleri süreyi kat kat değiştirir. Veri Yapıları kursundaki önbellek ölçümünde bu etki, ölçülmek isteneni gizleyecek kadar büyüktü.

Girdi. Aynı algoritma farklı girdilerde farklı sürer; sıralı bir dizi ile karışık bir dizi aynı sıralama algoritmasında bambaşka davranır.

Ölçüm bu nedenle bir algoritmanın özelliği değil, belirli bir çalıştırmanın gözlemidir. Karşılaştırmanın taşınabilir olması için, donanımdan ve dilden bağımsız bir ölçüt gerekir.

Hesaplama Modeli ve İşlem Sayımı

Çözüm, soyut bir hesaplama modeli benimsemektir. Bu kursta kullanılan model şu varsayımlara dayanır:

• Temel işlemler — toplama, karşılaştırma, atama, dizin erişimi — sabit sürede yapılır.
• Bellek erişimi konumdan bağımsız olarak aynı maliyettedir.
• İşlemler sırayla yürütülür.

Model, gerçekliğin sadeleştirilmiş hâlidir: önbellek katmanları ve komut boru hattı yok sayılır. Karşılığında, algoritmalar donanımdan bağımsız karşılaştırılabilir hâle gelir.

Ölçüt de buradan çıkar: girdi büyüklüğüne göre yapılan temel işlem sayısı.

def dogrusal_arama(dizi: list[int], hedef: int) -> tuple[int, int]:
    """(bulunan dizin veya -1, karşılaştırma sayısı) döndürür."""
    karsilastirma = 0
    for i, deger in enumerate(dizi):
        karsilastirma += 1
        if deger == hedef:
            return i, karsilastirma
    return -1, karsilastirma


dizi = list(range(1000))
print(dogrusal_arama(dizi, 0))       # (0, 1)      — en iyi durum
print(dogrusal_arama(dizi, 999))     # (999, 1000) — en kötü durum
print(dogrusal_arama(dizi, -1))      # (-1, 1000)  — bulunamadı

Aynı algoritma, aynı girdi boyutunda 1 ile 1000 arasında değişen sayıda işlem yapar. Bu nedenle tek bir sayı yerine üç ayrı ölçüt tanımlanır:

• En iyi durum: En az işlem gerektiren girdi.
• En kötü durum: En çok işlem gerektiren girdi.
• Ortalama durum: Girdilerin bir olasılık dağılımı üzerinden beklenen işlem sayısı.

Varsayılan ölçüt en kötü durumdur; bir güvence verir ve dağılım varsayımı gerektirmez. Ortalama durum, dağılım gerçekten biliniyorsa anlamlıdır — karma tablosunun “ortalama sabit” vaadi tam olarak böyle bir iddiaydı.

Özet

• Algoritma; girdi, çıktı, belirlilik, sonluluk ve etkinlik ölçütlerini sağlayan sonlu adımlar dizisidir.
• Problem bir belirtimdir, örnek tek bir girdidir, program bir gerçekleştirimdir; doğruluk belirtime göre ölçülür.
• Doğruluk iki parçadır: kısmi doğruluk (durursa sonuç doğru) döngü değişmeziyle, sonlanma (her girdide durur) azalan bir büyüklükle gerekçelendirilir.
• Aynı problemin çözümleri yapı olarak farklılaşır; fark, maliyetin girdiyle büyüyüp büyümemesinde ortaya çıkar.
• Çalışma süresi donanıma, gerçekleştirime ve girdiye bağlıdır; algoritmanın özelliği değildir.
• Ölçüt, soyut bir modelde girdi büyüklüğüne göre yapılan temel işlem sayısıdır ve en iyi, en kötü ile ortalama durum ayrı ayrı ele alınır.

Sonraki Adım

İşlem sayımı doğru yönde bir adımdır ama hâlâ ayrıntıya boğulur: bin elemanlık dizide 1000 mü, 1002 mi karşılaştırma yapıldığı önemsizdir. Sonraki ders, bu ayrıntıyı eleyip yalnızca büyüme hızını tutan gösterimi — asimptotik gösterimi — biçimsel olarak tanımlayacak.