--- title: 'İki İşaretçi' source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/iki-isaretci' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:31+00:00' license: 'CC BY-SA 4.0' --- # İki İşaretçi Sıralı dizide karşılıklı tarama; ön koşul bozulduğunda ortaya çıkan 25 yanlış yanıt ve ön koşulu sağlamanın adım bedeli. Önceki konu bir algoritmanın doğruluğunun **olasılıkla** ifade edilebileceğini gösterdi: beklenen başarım bir dağılımdır, tek koşum bir örnektir. Bu konu farklı bir belirsizlik kaynağıyla açılıyor ve bu kaynak olasılıksal değil **yapısaldır**. Bir problem çözme kalıbı seçmek bir hızlanma satın almak değil, bir **ön koşulu kabul etmektir**. Ön koşul sağlandığı sürece kalıp hem doğru hem ucuzdur. Sağlanmadığında kalıp durmaz, uyarmaz, yavaşlamaz — **yanlış yanıt verir**, ve yanlışlığı çıktısına bakarak anlaşılmaz. Bu yüzden konunun sekiz dersinin sekizi de aynı çerçeveyi kurar: bir **kâhin** (kaba kuvvet, her zaman doğru, her zaman pahalı), bir **kalıp**, ve ikisinin **ayrıldığı girdi sayısı**. İlk kalıp iki işaretçidir; ön koşulu tek cümledir: **dizi sıralı olmalı**. ## Problem, Kâhin ve Kalıp Problem şudur: bir dizide **toplamı hedefe eşit iki ayrı konum** var mı. Kâhin bütün çiftleri dener; n değerli dizide $n(n-1)/2$ çift vardır ve kâhin gerektiğinde hepsine bakar. Kalıp iki işaretçiyi dizinin iki ucuna koyar, toplam hedeften küçükse soldakini sağa, büyükse sağdakini sola kaydırır. **PK1.** Ölçü **adımdır**, süre değildir. Sayaç her karşılaştırmayı bir adım sayar ve gerçek zaman hiçbir yerde ölçülmez. **PK2.** Dağarcık belirlenimci bir üreteçten gelir; tohum `20260218`. Aynı tohum aynı 40 diziyi verir. **PK3.** Her dizi 12 değer taşır, değerler −9 ile 20 arasındadır. **PK4.** Kâhin kaba kuvvettir ve **her zaman doğru** sayılır. Kalıbın doğruluğu ancak kâhinle karşılaştırılarak iddia edilir. **PK5.** Ön koşulu sağlayan öbek, aynı 40 dizinin **sıralanmış** biçimidir; başka bir üreteçten gelmez. İki öbeğin tek farkı sıradır. ```python TOHUM, UZUNLUK, DAGARCIK = 20260218, 12, 40 def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def dagarcik(tohum=TOHUM, n=DAGARCIK, uzunluk=UZUNLUK): r = uretec(tohum) return [{"no": i + 1, "dizi": [r(30) - 9 for _ in range(uzunluk)]} for i in range(n)] class Sayac: def __init__(self): self.adim = 0 def say(self, n=1): self.adim += n def kahin_ciftler(dizi, hedef, s): """Butun ciftleri dener. Her zaman dogru, her zaman pahali.""" for i in range(len(dizi)): for j in range(i + 1, len(dizi)): s.say() if dizi[i] + dizi[j] == hedef: return True return False def kalip_iki_isaretci(dizi, hedef, s): """ONKOSUL: dizi sirali olmali.""" sol, sag = 0, len(dizi) - 1 while sol < sag: s.say() t = dizi[sol] + dizi[sag] if t == hedef: return True if t < hedef: sol += 1 else: sag -= 1 return False def olc(kume, hedef): ayrilan, ak, ah = [], 0, 0 for k in kume: s1, s2 = Sayac(), Sayac() a = kalip_iki_isaretci(k["dizi"], hedef, s1) b = kahin_ciftler(k["dizi"], hedef, s2) ak, ah = ak + s1.adim, ah + s2.adim if a != b: ayrilan.append(k["no"]) return {"ayrilan": len(ayrilan), "ilk_ayrilan": ayrilan[:6], "kalip_adim": ak, "kahin_adim": ah, "oran": round(ah / ak, 2)} K = dagarcik() S = [dict(k, dizi=sorted(k["dizi"])) for k in K] print("dagarcik:", len(K), "dizi x", UZUNLUK, "deger | kendiliginden sirali:", sum(1 for k in K if k["dizi"] == sorted(k["dizi"]))) for ad, kume in (("on_kosul saglaniyor", S), ("on_kosul bozuk ", K)): print(f" {ad}", olc(kume, 11)) ``` ``` dagarcik: 40 dizi x 12 deger | kendiliginden sirali: 0 on_kosul saglaniyor {'ayrilan': 0, 'ilk_ayrilan': [], 'kalip_adim': 154, 'kahin_adim': 972, 'oran': 6.31} on_kosul bozuk {'ayrilan': 25, 'ilk_ayrilan': [1, 2, 3, 6, 8, 9], 'kalip_adim': 372, 'kahin_adim': 866, 'oran': 2.33} ``` Üç sayı yan yana duruyor. Ön koşul sağlandığında kalıp **40 girdinin 40'ında** kâhinle aynı yanıtı veriyor ve **154** adım harcıyor; kâhin **972** adım harcıyor, oran **6,31**. Ön koşul bozulduğunda ayrılan girdi **25** oluyor ve oran **2,33'e** düşüyor. İkinci satırın en önemli tarafı ayrılan girdi sayısı değil, ikisinin birlikte olmasıdır. **Yanlışlık ucuz da değildir:** kalıbın adımı 154'ten 372'ye çıkıyor, çünkü sırasız dizide işaretçiler doğru çifti bulamadan uçlarda buluşuyor ve kalıp erken çıkamıyor. Hızlanma 6,31 kattan 2,33 kata düşerken doğruluk da gidiyor. ## Ayrılan Girdide Ne Oluyor Ayrılmanın nedeni tek bir yerdedir. Kalıp, "toplam küçükse soldakini büyüt" kuralını uygularken **soldaki değerin sağa doğru büyüdüğünü** varsayar. Sıralı olmayan dizide bu varsayım yanlıştır; işaretçi bir kez yanlış yöne kaydırıldığında atlanan konumlara bir daha dönülmez. ```python def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def dagarcik(tohum): r = uretec(tohum) return [[r(30) - 9 for _ in range(12)] for _ in range(40)] def kahin_ciftler(dizi, hedef): for i in range(len(dizi)): for j in range(i + 1, len(dizi)): if dizi[i] + dizi[j] == hedef: return True, (dizi[i], dizi[j]) return False, None def kalip_iki_isaretci(dizi, hedef): sol, sag = 0, len(dizi) - 1 while sol < sag: t = dizi[sol] + dizi[sag] if t == hedef: return True if t < hedef: sol += 1 else: sag -= 1 return False ilk = dagarcik(20260218)[0] print("girdi 1 :", ilk) print(" kalip :", kalip_iki_isaretci(ilk, 11)) print(" kahin :", kahin_ciftler(ilk, 11)) print(" sirali :", sorted(ilk), "-> kalip", kalip_iki_isaretci(sorted(ilk), 11)) print() print("tohum hedef on_kosul ayrilan/40") for tohum in (20260218, 20260219): for hedef in (11, 25): K = dagarcik(tohum) for ad, kume in (("saglaniyor", [sorted(d) for d in K]), ("bozuk ", K)): ayrilan = sum(1 for d in kume if kalip_iki_isaretci(d, hedef) != kahin_ciftler(d, hedef)[0]) print(f"{tohum} {hedef:5d} {ad} {ayrilan:8d}" f" oran {ayrilan / 40:.4f}") ``` ``` girdi 1 : [-8, -5, 2, -1, 2, 5, 4, 1, 16, 17, 6, -1] kalip : False kahin : (True, (-5, 16)) sirali : [-8, -5, -1, -1, 1, 2, 2, 4, 5, 6, 16, 17] -> kalip True tohum hedef on_kosul ayrilan/40 20260218 11 saglaniyor 0 oran 0.0000 20260218 11 bozuk 25 oran 0.6250 20260218 25 saglaniyor 0 oran 0.0000 20260218 25 bozuk 22 oran 0.5500 20260219 11 saglaniyor 0 oran 0.0000 20260219 11 bozuk 24 oran 0.6000 20260219 25 saglaniyor 0 oran 0.0000 20260219 25 bozuk 16 oran 0.4000 ``` Birinci girdide kâhin `(-5, 16)` çiftini buluyor; kalıp `False` döndürüyor. Aynı dizi sıralandığında kalıp da `True` döndürüyor. **Girdi değişmedi, yalnız sırası değişti** — kalıbın yanıtını değiştiren şey verinin içeriği değil, ön koşulun sağlanıp sağlanmadığıdır. **PK6.** Ayrılan girdi sayısı 40 üzerindendir. 40 girdide 1 ayrılma 0,0250'dir; 1 girdilik fark **ölçülmemiş sayılır**, 3 ve üzeri anlamlıdır. **PK7.** İkinci dağarcık `20260219` tohumundan gelir ve yalnız oranın **büyüklük düzenini** sınamak için kullanılır. İkinci dağarcıkta hedef 11 için ayrılan girdi **24**, birincide **25**. Hedef 25 için **16** ve **22**. Dört ölçümün dördünde de oran 0,40 ile 0,63 arasında, yani **aynı büyüklük düzeninde**; sonuç dağarcığa bağlı değildir. Ön koşulun sağlandığı dört satırda ayrılan girdi **sıfırdır** ve bu da dağarcıktan bağımsızdır. ## Ön koşulu Sağlamanın Bedeli Buraya kadarki ölçüm bir soruyu açıkta bırakıyor: dizi sıralı değilse **sıralanabilir**. O hâlde kalıp yine kullanılabilir. Ama sıralamanın kendisi bir adım harcar ve bu adım kalıbın hanesine yazılmalıdır. **PK8.** Ön koşulu sağlamanın bedeli ölçülürken sıralama **karşılaştırmalı** bir yordamla yapılır ve karşılaştırmaları adım olarak sayılır. Sıralama yordamlarının kendisi Algoritmalar kursunda ölçüldü; burada tekrarlanmaz, yalnız adımı sayılır. ```python def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def dagarcik(tohum=20260218): r = uretec(tohum) return [[r(30) - 9 for _ in range(12)] for _ in range(40)] class Sayac: def __init__(self): self.adim = 0 def say(self): self.adim += 1 def kahin_ciftler(dizi, hedef, s): for i in range(len(dizi)): for j in range(i + 1, len(dizi)): s.say() if dizi[i] + dizi[j] == hedef: return True return False def kalip_iki_isaretci(dizi, hedef, s): sol, sag = 0, len(dizi) - 1 while sol < sag: s.say() t = dizi[sol] + dizi[sag] if t == hedef: return True if t < hedef: sol += 1 else: sag -= 1 return False def sirala_sayarak(dizi, s): """Onkosulu saglamanin bedeli. Karsilastirmalar adim olarak sayilir.""" a = list(dizi) for i in range(1, len(a)): j = i while j > 0: s.say() if a[j - 1] <= a[j]: break a[j - 1], a[j] = a[j], a[j - 1] j -= 1 return a print("hedef dogru yalniz kalip siralama dahil kahin oran") for hedef in (11, 25): yalniz, dahil, kahin, dogru = 0, 0, 0, 0 for dizi in dagarcik(): sa, sk, sh = Sayac(), Sayac(), Sayac() y = kalip_iki_isaretci(sirala_sayarak(dizi, sa), hedef, sk) h = kahin_ciftler(dizi, hedef, sh) yalniz += sk.adim dahil += sa.adim + sk.adim kahin += sh.adim dogru += (y == h) print(f"{hedef:5d} {dogru:2d}/40 {yalniz:12d} {dahil:14d} {kahin:5d}" f" {kahin / dahil:5.2f}") ``` ``` hedef dogru yalniz kalip siralama dahil kahin oran 11 40/40 154 1737 866 0.50 25 40/40 352 1935 1564 0.81 ``` Doğruluk geri geldi: **40/40**. Ama oran **1'in altına düştü**. Hedef 11 için sıralama dahil toplam **1737** adım, kâhin **866** adım; kalıp kâhinin **iki katı** iş yapıyor. Hedef 25 için 1935'e karşı 1564, oran 0,81. Bu, konunun ikinci iddiasının ilk ödemesidir: **hızlandırma bazen hızlandırmaz.** Bu büyüklükte bir girdide iki işaretçi, ön koşulu kendisi sağlamak zorunda kaldığında kaba kuvvetten pahalıdır. Kalıbın kazandığı yer, sıralamanın **bir kez** yapılıp **çok kez** sorgulandığı ya da verinin zaten sıralı geldiği durumdur. Dizi uzadıkça denge değişir — sıralama $n \log n$, kâhin $n^2$ büyür — ama bu dağarcıkta 12 değer, dengeyi kaba kuvvetin lehine bırakacak kadar küçüktür. ## Adım Sayısı Doğruluk Hakkında Bir Şey Söylemez Yukarıdaki iki ölçümde ayrılma, adımda bir değişiklikle birlikte geldi: 154'ten 372'ye. Bu bir kural değildir ve buna güvenmek tehlikelidir. Aynı kalıbın sayan biçimi bunu gösterir. Problem şimdi "toplamı hedeften küçük **kaç çift** var" sorusudur; kalıp, sağ uçta bir çift sayıldığında aradaki bütün çiftlerin de sayılacağını kullanır. **PK9.** Sayan biçimde kalıp erken çıkamaz; her koşumda işaretçiler tam olarak n−1 adım atar. Adım sayısı bu yüzden girdinin içeriğinden bağımsızdır. ```python def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def dagarcik(tohum=20260218): r = uretec(tohum) return [[r(30) - 9 for _ in range(12)] for _ in range(40)] class Sayac: def __init__(self): self.adim = 0 def say(self): self.adim += 1 def kahin_kucuk_cift(dizi, hedef, s): """Toplami hedeften kucuk cift sayisi. Butun ciftler denenir.""" say = 0 for i in range(len(dizi)): for j in range(i + 1, len(dizi)): s.say() if dizi[i] + dizi[j] < hedef: say += 1 return say def kalip_kucuk_cift(dizi, hedef, s): """ONKOSUL: dizi sirali olmali. Sag ucta bir cift sayilirsa aradakiler de sayilir.""" sol, sag, say = 0, len(dizi) - 1, 0 while sol < sag: s.say() if dizi[sol] + dizi[sag] < hedef: say += sag - sol sol += 1 else: sag -= 1 return say print("on_kosul ayrilan/40 kalip kahin oran") for ad, hazirla in (("saglaniyor", sorted), ("bozuk ", list)): ayrilan, ak, ah = 0, 0, 0 for dizi in dagarcik(): d = hazirla(dizi) s1, s2 = Sayac(), Sayac() a = kalip_kucuk_cift(d, 6, s1) b = kahin_kucuk_cift(d, 6, s2) ak, ah = ak + s1.adim, ah + s2.adim ayrilan += (a != b) print(f"{ad} {ayrilan:8d} {ak:5d} {ah:5d} {ah / ak:5.2f}") ``` ``` on_kosul ayrilan/40 kalip kahin oran saglaniyor 0 440 2640 6.00 bozuk 39 440 2640 6.00 ``` İki satırın adım sütunları **birebir aynı**: kalıp 440, kâhin 2640, oran 6,00. Ayrılan girdi sütunu ise 0'dan **39'a** çıkıyor — 40 girdinin 39'unda kalıp yanlış bir sayı döndürüyor. Kalıp yine bir tam sayı veriyor, yine altı kat hızlı, yine hiçbir uyarı üretmiyor. Bu, konunun üçüncü iddiasının neden gerekli olduğunu gösteriyor. Adım sayısı bir başarım ölçüsüdür ve **doğruluk hakkında hiçbir şey söylemez**. Kaba kuvvet burada bir "yavaş seçenek" değil, 39 yanlış yanıtı görünür kılan **tek** araçtır. Kâhin olmasaydı bu tablonun iki satırı ayırt edilemezdi. ## Üç Sayı | Ölçüt | Kâhin | Kalıp | Ayrılan girdi | |---|---|---|---| | Ön koşul sağlanıyor (hedef 11) | 972 adım | 154 adım | **0/40** | | Ön koşul bozuk (hedef 11) | 866 adım | 372 adım | **25/40** | | Ön koşulu sağlayarak (hedef 11) | 866 adım | 1737 adım | **0/40** | | Sayan biçim, ön koşul bozuk | 2640 adım | 440 adım | **39/40** | Üç satır üç ayrı karar noktasıdır. Birinci satır kalıbın vaadidir. İkinci satır ön koşul denetlenmediğinde ne olduğunu gösterir: yanıtların yüzde altmış ikisi bozuk ve hızlanma üçte iki oranında erimiş. Üçüncü satır ön koşulu kendi elinle sağlamanın faturasıdır. Kalıbın bir denetim eklenerek güvenli kılınabileceği düşünülebilir: dizinin sıralı olup olmadığına bakılır, değilse kâhine dönülür. Bu denetim n−1 karşılaştırmadır, yani 40 dizi için 440 adım. Denetim **doğruluğu kurtarır** ama **hızlanmayı kurtarmaz**: sırasız girdide iş yine kâhine kalır. Ölçülmesi gereken şey denetimin maliyeti değil, girdilerin kaçının ön koşulu sağladığıdır. Bu dağarcıkta o sayı **sıfırdır**. ## Özet - Bir kalıp seçmek bir ön koşulu kabul etmektir; iki işaretçinin ön koşulu dizinin sıralı olmasıdır. - Ön koşul sağlandığında kalıp 40 girdinin 40'ında kâhinle aynı yanıtı veriyor ve 972 yerine 154 adım harcıyor; oran 6,31. - Ön koşul bozulduğunda kalıp **25 girdide** kâhinden ayrılıyor ve hızlanma 2,33 kata düşüyor; yanlışlık ucuz değildir. - İkinci dağarcıkta ayrılan girdi 24; oran aynı büyüklük düzeninde kaldığı için sonuç dağarcığa bağlı değildir. - Ön koşulu sıralayarak sağlamak doğruluğu geri getiriyor ama toplam adımı 1737'ye çıkarıyor ve kalıbı kâhinden pahalı kılıyor. ## Sonraki Adım İki işaretçi diziyi iki uçtan sıkıştırıyordu ve ön koşulu sıraydı. Sonraki kalıp işaretçileri aynı yönde tutar ve aralarındaki bölgeyi bir **pencere** gibi büyütüp küçültür; kazancı, pencere kaydıkça toplamı sıfırdan hesaplamak yerine artımlı güncellemesinden gelir. Ön koşulu da farklıdır ve sıraya hiç bakmaz: **hiçbir değer negatif olmamalıdır**. Sonraki ders bu ön koşulun bozulduğu 10 girdiyi kâhinle sayacak.