Bölüm 1: Giriş ve Algoritma Analizi

1.1Ders kitapları ve meslek sevgisi

Veri yapıları ve algoritmalar, bilgisayar mühendisliğinin geri kalanının üzerine kurulduğu temel derslerdendir. İşletim sistemi, derleyici, veri tabanı, ağ yazılımı ya da oyun motoru yazan her mühendis, verisini bellekte nasıl tutacağına ve onu hangi yöntemle işleyeceğine karar verir. Bu derste her yapı C diliyle gerçeklenir. C, belleği doğrudan gösterdiği için bir yapının bellekte nasıl durduğunu, bir işaretçinin neyi gösterdiğini ve ayrılan belleğin ne zaman geri verildiğini açıkça görmeyi sağlar.

1.1.1Ders kitapları

Dersin ana kitabı Horowitz, Sahni ve Anderson-Freed'in Fundamentals of Data Structures in C adlı kitabıdır. Bu notun konu sırası, örnekleri ve kodlarının çoğu bu kitabın birinci bölümünden gelir. Kitabın aslında üç sürümü vardır. İlk sürümdeki kodlar SPARKS adlı bir sözde dille yazılmıştı. Sonraki sürümlerde aynı içerik C ve C++ ile yeniden yazıldı. Konular ve sıralanışları hemen hemen aynıdır; değişen, kodların dilidir. C++ sürümü sınıflar ve şablonlar nedeniyle en kapsamlı olanıdır, ama bu derste C sürümü izlenir (Şekil 1.1).

Kitaplığın ikinci sırası Kernighan ve Ritchie'nin The C Programming Language kitabıdır. Dennis Ritchie C dilinin tasarımcısıdır; kitap da dilin her ayrıntısını kısa ve kesin biçimde anlatır. Bir işlecin önceliği, bir standart kütüphane fonksiyonunun dönüş değeri ya da bir bildirimin anlamı konusunda kuşku doğduğunda başvurulacak yer burasıdır. Bu yüzden bir başucu kitabı olarak el altında durmalıdır.

Ek kaynak olarak iki kitap önerilir. Cormen, Leiserson, Rivest ve Stein'ın Introduction to Algorithms kitabı, baş harflerinden dolayı kısaca CLRS diye anılır. Asimptotik gösterimi, en kötü ve ortalama durum analizini ve amortize analizi matematiksel olarak en sağlam biçimde anlatan kaynaktır. Sedgewick'in Algorithms in C kitabı ise aynı algoritmaları C koduyla ve çok sayıda ölçümle verir.

1.1.2Mesleği sevmek

Bir işin iyi yapılması büyük ölçüde o işin sevilmesine bağlıdır. Arkeolog bugün yaşar, ama aklı beş bin beş yüz yıl öncesindedir. Bir mezar odasına bakıp firavunun karısının oraya hangi sebeple gömülmüş olamayacağını tartışabilir. Astronom bir kara deliğin varlığını göstermek için yıllarca fotoğraf çeker ve bir yıldızın görüntüde bir piksel oynamasına sevinir. Bir futbol taraftarı sekiz saat yol gider, yüz elli liralık bilet alır, taş ve sopa tehlikesini göze alır. Aynı yolu bir bilimsel konferans için gideni ise çoğu kişi tuhaf karşılar. Üç örnekte de insanları zahmete katlandıran şey, yaptıkları işe duydukları ilgidir.

Programlamada da durum farklı değildir. Mesleğini seven kişi anlattığı şeyi içtenlikle anlatır ve dinlenir; işi baştan savma yapanı kimse dinlemez. Kod yazarken de kodun içinde yaşıyormuş gibi her satırda ne olup bittiği anlaşılmalıdır. Bir değişkenin o anda hangi değeri taşıdığı, bir işaretçinin hangi bellek hücresini gösterdiği, bir döngünün kaçıncı turda olduğu bilinmelidir. Bu notta kodların yanında verilen izleme tabloları tam olarak bu alışkanlığı kazandırmak içindir. Bir Çin atasözü bunu kısaca söyler: bir ömür mutlu olmanın yolu, işini sevmektir.

1.2Sistem yaşam döngüsü

Büyük bir yazılım bir oturuşta yazılmaz. Bir fikirden çalışan ve doğruluğuna güvenilen bir programa giden yol birbirini izleyen aşamalardan oluşur. Bu aşamaların bütününe sistem yaşam döngüsü (system life cycle) denir. Veri yapısı ve algoritma kararları bu döngünün belirli aşamalarında verilir; o yüzden döngüyü bilmek, bu derste öğrenilenlerin gerçek bir projede nereye oturduğunu görmeyi sağlar.

1.2.1Beş aşama

Horowitz ve Sahni yaşam döngüsünü beş aşamaya ayırır (Şekil 1.2):

1. Gereksinimler. Her proje, amacını belirten şartlarla başlar. Programcıya hangi girdilerin verileceği ve hangi çıktıların üretileceği bu aşamada yazılır. Örneğin bir öğrenci işleri programının girdisi öğrenci kayıtları ve notlar, çıktısı da transkriptler ve not ortalamalarıdır.
2. Çözümleme (analysis). Problem yönetilebilir parçalara ayrılır. Bunun iki yolu vardır: aşağıdan yukarı ve yukarıdan aşağı.
3. Tasarım. Problemin veri nesneleri ve bu nesneler üzerindeki işlemler belirlenir. Veri nesnelerinin tanımı bir soyut veri tipine, işlemlerin tanımı bir algoritmaya karşılık gelir. İkisi de programlama dilinden bağımsızdır. Tasarıma ayrılan zaman arttıkça sonraki aşamalarda çıkan hata azalır.
4. İnceltme ve kodlama. Veri nesneleri için gösterimler, yani somut veri yapıları seçilir ve algoritmalar bu yapıların üzerinde kodlanır. Verinin nasıl gösterildiği algoritmanın ne kadar etkin olacağını belirler. Aynı öğrenci listesi bir dizide ya da bir bağlı listede tutulabilir; aramanın ve eklemenin maliyeti bu seçime göre değişir.
5. Doğrulama. Programın doğruluğu ispat ve sınamayla gösterilir; bulunan hatalar giderilir. Bu üç etkinliğin her biri başlı başına bir araştırma alanıdır.

Şekildeki kesikli ok, döngünün tek yönlü bir boru hattı olmadığını gösterir. Doğrulama aşamasında bulunan bir hata kimi zaman yalnız bir satırın düzeltilmesini, kimi zaman bir veri yapısının baştan değiştirilmesini gerektirir. Hata ne kadar erken aşamadan kaynaklanıyorsa düzeltmesi o kadar pahalıdır. Gereksinimlerdeki bir yanlış anlama, kodlamadaki bir yazım hatasından çok daha fazla iş çıkarır.

1.2.2Çözümleme: aşağıdan yukarı, yukarıdan aşağı

Çözümleme aşamasında problemi parçalamanın iki yolu vardır.

Aşağıdan yukarı (bottom-up) yaklaşımda problem doğrudan parçalara bölünür ve her parçaya ayrı ayrı odaklanılır. Modüller baştan görülür; problem modül modül çözülür, sonra parçalar birleştirilir. Bu yol, benzer bir projeyi daha önce yapmış ve hangi modüllerin gerektiğini bilen ekipler için hızlıdır. Proje konusunda deneyim varsa tercih edilir.

Yukarıdan aşağı (top-down) yaklaşımda önce bir ana plan yapılır. Amacın ne olduğu ve son ürünün neye benzeyeceği sorulur. Problem bu plana göre alt problemlere, alt problemler de daha küçük parçalara bölünür. Bu yol daha çok zaman alır, ama geri dönüş ve hata olasılığı daha düşüktür. Konuda deneyim yoksa tercih edilir; çünkü parçalar bütünün içindeki yerleri bilinerek tanımlanır.

1.2.3Tasarım ve gerçeklemeyi ertelemek

Tasarım aşamasında verilen kararlar dilden bağımsızdır. Örneğin öğrenci kütüğünün hangi alanları içereceğine (numara, ad, bölüm, not listesi) bu aşamada karar verilir. Ama bu kütüğün bir dizi mi, bir bağlı liste mi, yoksa bir ağaç mı olarak gerçekleneceği ertelenebilir. Erteleme bir tembellik değil, bilinçli bir tercihtir. Programın hangi işlemleri ne sıklıkla yapacağı netleştikçe en uygun gerçekleme daha iyi seçilir. Kayıtlar çoğunlukla numarayla aranıyorsa sıralı bir dizi ya da bir arama ağacı uygundur. Sık sık ekleme ve silme yapılıyorsa bağlı liste öne çıkar.

Aynı düşünce kodlamanın kendisi için de geçerlidir: kodlama ne kadar geciktirilirse, arka planda o kadar iyi bir yöntem yakalanabilir. Problemi düşünmeden klavyeye oturmak, ilk akla gelen ve çoğu zaman en iyi olmayan yöntemle yola çıkmak demektir.

1.2.4Kodlama ve doğrulama

Doğrulama dört etkinliği kapsar.

• Doğruluk ispatı. Programın doğruluğu matematiksel tekniklerle ispatlanabilir. Küçük bir yordam için bu mümkündür, ama büyük bir projeyi baştan sona ispatlamak neredeyse imkânsızdır. Pratik yol, doğruluğu daha önce ispatlanmış algoritmaları kullanmaktır; böylece hata olasılığı azalır.
• Sınama (testing). Sınama için çalışan bir kod ve bütün senaryoları kapsayan test verisi gerekir. Boş girdi, tek öğeli girdi, en büyük girdi, sıralı ve ters sıralı girdi, tekrarlı değerler bu senaryoların başında gelir. Derleyicinin sözdizimi hatası vermemesi ve programın bir örnekte doğru çıktı üretmesi, programın doğru olduğunu göstermez.
• Hata giderme. İspat ya da testler bir hata gösterirse hata, tasarım ve kodlama kararları göz önüne alınarak ayıklanır. İyi belgelenmiş bir tasarım bu işi büyük ölçüde kolaylaştırır.
• İşletim zamanı. Hatasız ama yavaş çalışan bir programın da fazla değeri yoktur. Doğruluk ile verimlilik ayrı sorulardır; ikisine de ayrı ayrı cevap verilmelidir.

1.3Algoritma

Tasarım aşamasında işlemler bir algoritma olarak tanımlanır. Günlük dilde “bir işi yapmanın yolu” anlamında kullanılan bu sözcüğün bilgisayar biliminde kesin bir tanımı vardır.

1.3.1Tanım ve beş ölçüt

Beş ölçüt Tablo 1.1'de özetlenmiştir.

Ölçütleri tek tek açalım. Girdi ölçütü sıfır girdiye izin verir: “ilk on asal sayıyı yaz” diyen bir algoritma dışarıdan hiçbir şey almaz. Çıktı ölçütü ise en az bir sonuç ister; hiçbir şey üretmeyen bir yöntemin işe yarar bir görevi yoktur.

Kesinlik her komutun tek bir biçimde anlaşılmasını ister. “x'e 6 ya da 7 ekle” komutu kesin değildir, çünkü hangisinin ekleneceğini söylemez. “Sayıyı yeterince büyük bir değerle çarp” da kesin değildir. C gibi bir programlama dili bu ölçütü kendiliğinden sağlar: dilin her yapısının anlamı tanımlıdır. Doğal dille yazılan bir algoritmada ise kesinliğe ayrıca dikkat etmek gerekir.

Sonluluk, algoritmanın her girdi için bir noktada durmasını ister. “1'den başla, sayıyı ikiyle çarp, sonuç negatif olunca dur” komutu matematikte hiç durmaz. Etkinlik ise her komutun gerçekten yapılabilir olmasını ister. İki tamsayıyı toplamak etkin bir işlemdir. “π sayısının bütün basamaklarını yaz” komutu kesindir, ama sonlu zamanda yapılamadığı için etkin değildir.

1.3.2Algoritma ile hesaplama yöntemi

Sonluluk ölçütü ilginç bir sonuç doğurur: hiç sonlanmaması gereken programlar algoritma değildir. Bir işletim sistemi bilgisayar açık kaldığı sürece çalışır; bir görevi bekler, onu yürütür ve yeniden beklemeye geçer. Sona ermediği için tanım gereği bir algoritma sayılmaz. Bu tür programlara hesaplama yöntemi (computational procedure) denir. İşletim sisteminin içindeki parçalar ise, örneğin bir dosyayı diskten okuyan ya da bekleyen işler arasından sıradakini seçen yordam, sona erdikleri için birer algoritmadır.

Bir algoritma doğal dille, bir akış şemasıyla ya da bir programlama diliyle ifade edilebilir. Doğal dil kolay okunur ama kesinliği sağlamakta zorlanır. Akış şeması küçük algoritmalarda açıklayıcıdır, büyük algoritmalarda ise karmaşık bir çizime dönüşür. Bu derste algoritmalar C ile yazılır. Yer yer, bir fikri kodun ayrıntısına girmeden göstermek için C'ye benzeyen kısa bir sözde kod kullanılır.

1.4Soyut veri tipi

Tasarım aşamasında veri nesneleri dilden bağımsız olarak tanımlanır. Bu tanımın aracı soyut veri tipidir. Soyut veri tipi, bir verinin “ne yaptığını” onun “nasıl yapıldığından” ayırır. Bu ayrım, bu derste gerçeklenecek her yapının (yığın, kuyruk, liste, ağaç, çizge) ortak çerçevesidir.

1.4.1Veri tipi ve soyut veri tipi

C'deki int tipini düşünelim. Bu tip iki şeyden oluşur: belirli bir aralıktaki tamsayılar ve bu tamsayılar üzerinde tanımlı işlemler (+, -, *, /, %, karşılaştırmalar, atama). Bir int değişkenini kullanan programcı, sayının bellekte kaç bitle ve hangi kodlamayla tutulduğunu bilmek zorunda değildir. Toplama işleminin işlemcide nasıl yapıldığını da bilmez. Yalnız işlemlerin ne yaptığını bilir. Genel olarak bir veri tipi, nesnelerden ve bu nesneler üzerinde tanımlı işlemlerden oluşan bir topluluktur.

Bu tanımda iki kavram karşı karşıya durur.

• Belirtim, “NE yapılır?” sorusunun cevabıdır. İşlemlerin adlarını, parametrelerinin tiplerini, sonuçlarının tipini ve her işlemin ne yaptığını söyler. ADT'yi kullanan programcı yalnız bunu bilir.
• Gerçekleme, “NASIL yapılır?” sorusunun cevabıdır. Verinin bellekteki gösterimini (bir struct, bir dizi, bir bağlı liste) ve işlemleri yapan kodu içerir. Kullanıcıdan gizlenir.

Ayrımın yararı somuttur. Gerçekleme gizli olduğu için, belirtim değişmediği sürece gerçekleme rahatça değiştirilebilir. Dizi ile yazılmış bir yığın daha sonra bağlı listeyle yeniden yazılabilir; yığını kullanan programın tek satırı bile değişmez. Kullanıcı da gerçeklemenin iç ayrıntılarına bağımlı kod yazamaz, çünkü o ayrıntıları göremez. Aynı ADT birden çok veri yapısıyla gerçeklenebilir ve hangisinin seçileceği, yaşam döngüsünün inceltme aşamasına bırakılabilir.

Bir ADT'nin işlemleri görevlerine göre gruplanır:

• Kurucu (constructor) işlemler türün yeni bir örneğini yaratır.
• Dönüştürücü (transformer) işlemler var olan örneklerden yeni bir değer üretir.
• Gözlemci ya da raporlayıcı (observer, reporter) işlemler örnek hakkında bilgi verir, onu değiştirmez.

1.4.2Kesir ADT'sinin belirtimi

Soyut veri tipi kavramını küçük ama eksiksiz bir örnekle somutlaştıralım: kesirler. Bir kesir bir pay ve sıfırdan farklı bir paydadan oluşur. Kesirler üzerinde yaratma, toplama, eşitlik denetimi, yazdırma ve silme işlemleri tanımlansın. Belirtim, dilden bağımsız bir gösterimle şöyle yazılır:

ADT Kesir
  nesneler: pay/payda, payda ≠ 0
  işlemler:
    olustur(p, q)  → Kesir   /* kurucu */
    topla(a, b)    → Kesir   /* dönüştürücü */
    esit(a, b)     → Boolean /* gözlemci */
    yaz(a)                   /* raporlayıcı */
    sil(a)

Belirtimin ilk satırı nesneleri tanımlar: pay ve paydadan oluşan, paydası sıfır olmayan değerler. Sonraki satırlar işlemleri ve her birinin sonuç tipini verir. olustur(p, q) bir kurucudur. topla(a, b) iki kesirden yeni bir kesir ürettiği için dönüştürücüdür. esit(a, b) bir doğruluk değeri döndüren gözlemcidir; yaz(a) ise kesri ekrana yazan raporlayıcıdır. sil(a) kesrin kapladığı kaynağı geri verir. Belirtimde kesrin bellekte nasıl tutulacağına dair tek bir sözcük yoktur; olması da gerekmez.

Belirtim aynı zamanda bir ön koşul içerir: payda sıfır olamaz. Bu koşul, olustur işleminin paydası sıfır olan bir istek aldığında ne yapacağını belirlemeyi gerektirir. Bu soru gerçeklemede cevaplanır.

1.4.3C'de arayüz: başlık dosyası ve opak tip

C'nin sınıf kavramı yoktur, ama belirtim ile gerçeklemeyi ayırmak için iki araç sunar: başlık dosyası (header file) ve eksik tip (incomplete type). Başlık dosyası (.h), tip ve fonksiyon bildirimlerini taşır ve #include ile başka dosyalara eklenir. Gerçekleme ise ayrı bir kaynak dosyada (.c) durur. Kesir ADT'sinin arayüzü şudur:

/* kesir.h : arayuz (NE?) */
#ifndef KESIR_H
#define KESIR_H
typedef struct kesir Kesir; /* opak */

Kesir *kesir_olustur(int pay, int payda);
Kesir *kesir_topla(const Kesir *a,
                   const Kesir *b);
int  kesir_esit(const Kesir *a,
                const Kesir *b);
void kesir_yaz(const Kesir *k);
void kesir_sil(Kesir *k);
#endif

Dosyanın satırları şöyle çalışır:

• #ifndef KESIR_H, #define KESIR_H ve en sondaki #endif bir içerme korumasıdır. Bu üç satır önişlemciye yöneliktir. Dosya aynı derleme biriminde ikinci kez #include edilirse KESIR_H zaten tanımlı olduğu için içerik atlanır ve aynı bildirimler iki kez yapılmaz.
• typedef struct kesir Kesir; satırı iki iş yapar. Önce struct kesir adlı bir yapının var olduğunu bildirir, ama alanlarını söylemez. Sonra bu yapıya Kesir diye kısa bir ad verir. Alanları bilinmeyen bir yapı eksik tiptir: derleyici boyunu bilmez. Bu yüzden kesir.h'yi kullanan bir dosya Kesir tipinde bir değişken tanımlayamaz, k->pay gibi bir alana erişemez. Yalnız Kesir * tipinde bir işaretçi tutabilir. Alanları kullanıcıdan gizlenen böyle bir tipe opak tip (opaque type) denir.
• Beş fonksiyon bildirimi ADT'nin beş işlemine karşılık gelir. Kesirler hep işaretçiyle taşınır. Kesri yalnız okuyan işlemlerin parametreleri const Kesir * tipindedir; bu, fonksiyonun gösterilen kesri değiştirmeyeceğine dair derleyicinin denetlediği bir sözdür.

Gerçeklemenin ilk kısmı yapının alanlarını ve kurucuyu içerir:

/* kesir.c : gercekleme (NASIL?) */
#include <stdio.h>
#include <stdlib.h>
#include "kesir.h"

struct kesir { int pay, payda; };

Kesir *kesir_olustur(int pay, int payda) {
  Kesir *k;
  if (payda == 0) return NULL;
  k = malloc(sizeof *k);
  if (k == NULL) return NULL;
  k->pay = pay;
  k->payda = payda;
  return k;
}

struct kesir { int pay, payda; }; satırı yapıyı tamamlar. Bu satır yalnız kesir.c içinde göründüğü için alanlar yalnız bu dosyada bilinir. Opak tip yaklaşımı, ADT'nin “gerçekleme gizlidir” ilkesinin C'deki karşılığıdır.

kesir_olustur fonksiyonu satır satır şunu yapar:

1. Payda sıfırsa kesir yaratılamaz; fonksiyon NULL döndürür. NULL, hiçbir nesneyi göstermeyen boş işaretçidir (null pointer) ve burada “başarısız” anlamı taşır.
2. malloc(sizeof *k) çağrısı, bir struct kesir büyüklüğünde bellek ayırır. malloc, istenen bayt sayısında bir bellek bloğunu heap bölgesinden ayırır ve bloğun başlangıç adresini döndürür. sizeof *k ifadesi, k'nin gösterdiği tipin, yani struct kesir'in boyunu verir. Tip adını yeniden yazmak yerine *k kullanmak, ileride k'nin tipi değişirse boyun da kendiliğinden doğru kalmasını sağlar. sizeof işleneni değerlendirmez; k henüz bir değer almamış olsa da ifade güvenlidir.
3. Bellek kalmamışsa malloc NULL döndürür. Bu durum denetlenir ve fonksiyon da NULL döndürür. Denetim yapılmasaydı bir sonraki satır boş işaretçinin gösterdiği yere yazmaya çalışır ve program çökerdi.
4. k->pay = pay; satırındaki -> ok işlecidir: işaretçinin gösterdiği yapının alanına erişir. k->pay, (*k).pay ile aynı anlamdadır.
5. Son olarak yeni kesrin adresi döndürülür.

Fonksiyonun yerel değişkeni k, fonksiyon dönünce yok olur. Ama malloc ile ayrılan blok yaşamaya devam eder; çünkü heap'teki bir blok, free ile geri verilene kadar ayrılmış kalır. Fonksiyonun döndürdüğü adres bu bloğu gösterdiği için çağıran taraf kesri kullanabilir. Bir yerel değişkenin adresi döndürülseydi durum farklı olurdu: fonksiyonun çerçevesi yok olduktan sonra o adres geçersiz kalır.

1.4.4Gerçeklemenin kalanı

kesir.c dosyasının devamında kalan dört işlem yer alır:

Kesir *kesir_topla(const Kesir *a,
                   const Kesir *b) {
  return kesir_olustur(
      a->pay * b->payda
        + b->pay * a->payda,
      a->payda * b->payda);
}
int kesir_esit(const Kesir *a,
               const Kesir *b) {
  return a->pay * b->payda
      == b->pay * a->payda;
}
void kesir_yaz(const Kesir *k) {
  printf("%d/%d\n", k->pay, k->payda);
}
void kesir_sil(Kesir *k) { free(k); }

kesir_topla ortak payda formülünü uygular: a/b + c/d = (a·d + c·b) / (b·d). Sonucu kendisi ayırmaz, kesir_olustur'u çağırır. Böylece payda denetimi ve bellek ayırma tek bir yerde kalır. İki payda da sıfırdan farklı olduğu için çarpımları da sıfırdan farklıdır; kesir_olustur ancak bellek tükenirse NULL döndürür. Gerçekleme sonucu sadeleştirmez: 1/2 + 1/2 işleminin sonucu 4/4 olur. Sadeleştirme istenirse, sonucu en büyük ortak bölene bölen bir satır eklenebilir; bu ekleme arayüzü değiştirmez.

kesir_esit iki kesrin eşitliğini çapraz çarpımla denetler: a/b = c/d ancak ve ancak a·d = c·b ise. Bu yöntem sadeleştirilmemiş kesirlerde de doğru çalışır; 2/4 ile 1/2 eşit bulunur. C'de karşılaştırma işleci int tipinde 1 ya da 0 üretir; bu yüzden fonksiyon doğrudan karşılaştırmanın sonucunu döndürür. Belirtimdeki Boolean, C'de bu int değerle temsil edilir.

kesir_yaz kesri pay/payda biçiminde yazar. kesir_sil ise kesrin bloğunu free ile heap'e geri verir. free, malloc ile ayrılmış bir bloğu sisteme iade eder. Standart C, free(NULL) çağrısının hiçbir şey yapmadığını garanti eder; bu yüzden kesir_sil boş işaretçiyle de güvenle çağrılabilir.

1.4.5Arayüzü kullanmak: sözleşme ve sahiplik

Kesirleri kullanan program yalnız arayüzü bilir:

/* main.c : yalnizca arayuzu bilir */
#include "kesir.h"
#include <stddef.h> /* NULL */
int main(void) {
  Kesir *a = kesir_olustur(1, 2);
  Kesir *b = kesir_olustur(1, 3);
  Kesir *t = NULL;
  if (a && b) t = kesir_topla(a, b);
  if (t) kesir_yaz(t);  /* 5/6 */
  kesir_sil(a); kesir_sil(b);
  kesir_sil(t);  /* free(NULL) zararsiz */
  return 0;
}

main.c yalnız kesir.h'yi ve NULL sabiti için <stddef.h> başlığını içerir. struct kesir'in alanlarını görmez. Program üç dosyadan oluşur ve derlenirken iki kaynak dosya birlikte verilir; örneğin cc kesir.c main.c. Derleyici her .c dosyasını ayrı derler, bağlayıcı da main.c'deki çağrıları kesir.c'deki tanımlara bağlar.

Programın akışı Tablo 1.2'de izlenmiştir. Tablodaki adresler, bloğun yerini anlatmak için seçilmiş örnek değerlerdir; gerçek adresler her çalıştırmada farklı olabilir.

Programın son satırlarından sonra a, b ve t değişkenleri hâlâ eski adresleri taşır, ama bu adresler artık geçerli bir nesneyi göstermez. Böyle işaretçilere sarkan işaretçi (dangling pointer) denir. Onları kullanmak tanımsız davranıştır. Program hemen sona erdiği için burada bir sorun çıkmaz.

Arayüzü güvenle kullanmak için iki kural açıkça yazılmalıdır.

• Sözleşme. kesir_olustur, payda sıfırsa ya da bellek kalmamışsa NULL döndürür. Çağıran taraf bu sonucu denetlemekle yükümlüdür. main'deki if (a && b) ve if (t) denetimleri bu sözleşmenin gereğidir. Denetim yapılmasaydı kesir_topla(a, b) boş bir işaretçinin alanını okumaya çalışabilirdi.
• Sahiplik. kesir_olustur ve kesir_topla'nın döndürdüğü her kesir çağırana aittir. Çağıran, kesirle işi bitince onu kesir_sil ile bırakmalıdır. Bırakılmayan blok program bitene kadar heap'te kalır. Artık hiçbir işaretçiyle erişilemeyen ama geri verilmemiş belleğe bellek sızıntısı (memory leak) denir. Döngü içinde her turda bir kesir yaratıp silmeyi unutan bir program, bellek bitene kadar büyür.

t'nin başlangıçta NULL yapılmasının nedeni de sahiplik kuralıdır. a ya da b yaratılamazsa kesir_topla hiç çağrılmaz ve t NULL kalır. Programın sonundaki kesir_sil(t) çağrısı bu durumda free(NULL)'a dönüşür ve zararsızdır. Başlangıç değeri verilmeseydi t rastgele bir adres taşıyabilir ve free çağrısı programı çökertebilirdi.

1.5Seçimli sıralama

Algoritma kavramını ve C ile yazılışını ilk kez somut bir problem üzerinde görelim: bir tamsayı dizisini küçükten büyüğe sıralamak. Sıralama (sorting), öğeleri anahtarlarına göre artan ya da azalan düzene koymaktır. Bu problemin pek çok çözümü vardır. Bu kesimde en kolay anlaşılanlardan biri olan seçimli sıralama, önce bir fikir olarak, sonra sözde kodla, en sonunda da C koduyla verilir. Bir fikrin adım adım koda dönüşmesi, algoritma tasarımının olağan yoludur.

1.5.1Fikir

n öğeli sıralı olmayan bir list dizisi verilsin. Seçimli sıralama (selection sort) şu fikre dayanır: dizinin sıralanmamış kısmındaki en küçük öğe bulunur ve bu kısmın başına konur. Sonra sıralanmamış kısım bir öğe kısalır ve aynı iş tekrarlanır. İlk turda bütün dizinin en küçüğü list[0]'a, ikinci turda kalanların en küçüğü list[1]'e yerleşir. Genel olarak i. turda list[i] … list[n-1] aralığının en küçüğü list[i]'ye taşınır. Fikir C'ye benzeyen bir sözde kodla şöyle yazılır:

for (i = 0; i < n; i++) {
    list[i] .. list[n-1] arasini incele;
    en kucuk tamsayi list[min] olsun;
    list[i] ile list[min]'i takas et;
}

Bu sözde kodun ikinci ve üçüncü satırları henüz C değildir; “aralığı incele” ve “en küçük öğe bulunsun” gibi ifadeler bir C derleyicisinin anlayacağı komutlar değildir. Ama fikir açıktır ve bu satırların her biri kolayca C'ye çevrilir. En küçük öğeyi bulmak için aralık soldan sağa taranır; o ana kadar görülen en küçüğün indisi bir min değişkeninde tutulur. Takas işlemi de üç atamayla yapılır.

Şekil 1.3, algoritmanın her turda koruduğu durumu gösterir. Dizi kesikli çizgiyle iki bölgeye ayrılır. Soldaki sıralı bölge dizinin en küçük i öğesini sıralı biçimde tutar; bu öğeler bir daha yer değiştirmez. Sağdaki sıralanmamış bölge kalan öğeleri tutar. Her tur sıralı bölgeyi bir öğe büyütür. Bu durum her turun başında doğrudur ve algoritmanın doğruluğunun gerekçesidir. n − 1 tur sonunda sıralı bölgede en küçük n − 1 öğe vardır; kalan tek öğe de en büyük olduğu için son hücrede durur. Dizi sıralanmıştır.

Yazılmış bir algoritma olduğu gibi kabul edilmek zorunda değildir. Onu anlamak, zayıf yanlarını görmek ve gerekirse daha iyisini önerebilmek, bu dersin ulaşmak istediği düzeydir. Seçimli sıralama da bu gözle incelenecektir: kaç karşılaştırma yapar, kaç takas yapar, girdinin sıralı olması işini kolaylaştırır mı?

1.5.2C gerçeklemesi

Önce sıralama fonksiyonunu kullanan ana program:

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 101
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))
void sort(int list[], int n);

int main(void) {
  int i, n, list[MAX_SIZE];
  printf("Dizi boyunu giriniz: ");
  if (scanf("%d", &n) != 1 || n < 1 || n > MAX_SIZE) {
    printf("Hatali n degeri!\n");
    return 1;
  }
  for (i = 0; i < n; i++) list[i] = rand() % 100;
  sort(list, n);
  for (i = 0; i < n; i++) printf("%d ", list[i]);
  return 0;
}

Ana program satır satır şöyle çalışır:

• #define MAX_SIZE 101 dizinin en büyük boyunu bir sabitle verir. Sabit değiştirilince dizinin boyu da, sınır denetimi de kendiliğinden değişir.
• #define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t)) bir makrodur. Makro, #define ile tanımlanan ve derlemeden önce metin olarak yerine konan bir addır. SWAP(list[i], list[min], temp) yazılan yere önişlemci ((temp) = (list[i]), (list[i]) = (list[min]), (list[min]) = (temp)) metnini koyar. Virgül işleci üç atamayı soldan sağa sırayla yapar.
• void sort(int list[], int n); bir fonksiyon bildirimidir (prototip). sort'un tanımı main'den sonra geldiği için derleyiciye önceden fonksiyonun parametre tipleri ve dönüş tipi bildirilir.
• scanf("%d", &n) kullanıcıdan dizinin boyunu okur. &n, n'nin adresidir; scanf okuduğu değeri bu adrese yazar. scanf başarıyla okuduğu öğe sayısını döndürür. Kullanıcı sayı yerine harf girerse 1 dışında bir değer döner.
• Koşul üç durumu reddeder: okuma başarısız, n < 1 ya da n > MAX_SIZE. Son denetim önemlidir. list dizisinde MAX_SIZE hücre vardır; daha büyük bir n kabul edilseydi döngüler dizinin sonundan sonraki belleğe yazardı. C bu tür taşmaları denetlemez.
• rand() % 100 0 ile 99 arasında sözde rastgele bir sayı üretir. srand çağrılmadığı için program her çalıştırmada aynı diziyi üretir; bu, sonuçların tekrarlanabilmesi için bir kolaylıktır.
• sort(list, n) çağrısında dizinin kendisi değil, ilk öğesinin adresi gönderilir. sort içindeki list[i] ifadesi bu adresten başlayan belleğe erişir; bu yüzden sort'un dizide yaptığı değişiklikler main'deki diziyi değiştirir.

Sıralama fonksiyonu sözde kodun doğrudan C karşılığıdır:

void sort(int list[], int n) {
  int i, j, min, temp;
  for (i = 0; i < n - 1; i++) {
    min = i;
    for (j = i + 1; j < n; j++)
      if (list[j] < list[min])
        min = j;
    SWAP(list[i], list[min], temp);
  }
}

• Dış döngü i = 0'dan n - 2'ye kadar döner. Sözde kodda döngü n kez dönüyordu; son tur gereksizdir, çünkü tek öğelik aralık zaten sıralıdır. Bu yüzden döngü koşulu i < n - 1 olarak yazılır.
• min = i; aralığın ilk öğesini geçici olarak en küçük kabul eder.
• İç döngü j = i + 1'den n - 1'e kadar aralığın kalan öğelerini tarar. list[j] < list[min] ise daha küçük bir öğe bulunmuştur ve min güncellenir. İç döngü bittiğinde min, aralığın en küçük öğesinin indisidir.
• SWAP(list[i], list[min], temp) bu öğeyi aralığın başına taşır. min zaten i'ye eşitse takas bir öğeyi kendisiyle değiştirir; sonuç değişmez, yalnız üç gereksiz atama yapılır.

Program n = 10 girdisiyle derlenip çalıştırıldığında rastgele üretilen on sayıyı sıralı olarak yazar. Bu notun hazırlandığı ortamda çıktı 0 24 34 41 58 62 64 67 69 78 oldu. rand()'ın ürettiği dizi C kütüphanesine bağlıdır; başka bir derleyicide sayılar farklı çıkar, ama hep artan sırada yazılır.

1.5.3Kod izleme: {29, 10, 14, 37, 13}

sort fonksiyonunu beş öğeli {29, 10, 14, 37, 13} dizisiyle izleyelim. Tablo 1.3 her turda iç döngünün bulduğu min değerini ve takastan sonraki diziyi verir.

Birinci turda en küçük öğe 10 indis 1'de bulunur ve 29 ile yer değiştirir. İkinci turda tarama önce 14'ü, sonra 13'ü en küçük kabul eder; 13, indis 1'deki 29 ile takas edilir. Üçüncü turda 14 zaten aralığın en küçüğüdür; SWAP çalışır ama bir şey değiştirmez. Dördüncü ve son turda 29 ile 37 yer değiştirir. Dış döngü i = 4 olduğunda i < n - 1 koşulu yanlış çıkar ve fonksiyon biter. Toplam 4 + 3 + 2 + 1 = 10 karşılaştırma yapılmış, SWAP dört kez çağrılmış, bunların üçünde iki farklı hücre gerçekten yer değiştirmiştir.

1.5.4Analiz

Seçimli sıralamanın yaptığı karşılaştırma sayısı girdinin değerlerine bağlı değildir; yalnız n'ye bağlıdır. i. turda iç döngü j = i + 1, …, n − 1 değerlerini alır, yani n − 1 − i karşılaştırma yapar. Bütün turların toplamı:

(n − 1) + (n − 2) + … + 1 = n(n − 1) / 2

Bu toplam, ilk n − 1 doğal sayının toplamıdır. Formül şöyle doğrulanır: toplamı bir kez baştan, bir kez sondan yazıp terim terim toplayınca her çift n eder ve n − 1 çift vardır; toplamın iki katı n(n − 1)'dir. n = 5 için 5 · 4 / 2 = 10 karşılaştırma bulunur; izleme tablosundaki sayı da budur. n = 1000 için yaklaşık yarım milyon karşılaştırma gerekir. Karşılaştırma sayısı n² ile orantılı büyüdüğü için seçimli sıralamanın zamanı O(n²)'dir. O(n²) yazımı, büyük n için adım sayısının n²'nin sabit bir katını aşmadığını anlatır.

Takas sayısı ise azdır: her turda tek bir SWAP yapılır, toplam n − 1 kez. Bu yüzden takas en fazla n − 1 kez gerçekleşir. Öğeler büyük kayıtlarsa ve taşınmaları pahalıysa bu özellik seçimli sıralamayı çekici kılar. Algoritma ek bellek olarak yalnız i, j, min ve temp değişkenlerini kullanır. Dizi kendi yerinde sıralanır.

1.5.5Hatalı bir sort() sürümü

Seçimli sıralama yazılmak istendiğinde sık rastlanan bir kod şudur:

void sort(int list[], int n) {
  int i, j, min, temp;
  for (i = 0; i < n; i++) {
    min = i;
    for (j = 0; j < n; j++)
      if (list[j] > list[min]) {
        min = j;
        SWAP(list[i], list[min], temp);
      }
  }
}

Bu kod şaşırtıcı biçimde diziyi yine sıralar. Bu notu hazırlarken n ≤ 7 için bütün permütasyonlar denendi; hepsinde sonuç sıralı çıktı. Ama kod sözde koddaki seçimli sıralama değildir. Üç fark vardır:

1. İç döngü j = i + 1'den değil j = 0'dan başlar; her turda bütün diziyi tarar.
2. Koşul < değil >'dir; en küçük değil, o ana kadarki en büyük öğe aranır.
3. Takas iç döngüden sonra bir kez değil, koşul her doğru çıktığında iç döngünün içinde yapılır.

Sonuç doğru olsa da maliyet çok farklıdır. Tablo 1.4, iki sürümün aynı girdilerde yaptığı karşılaştırma ve takas sayılarını verir. Değerler iki sürüme sayaç eklenerek ölçülmüştür. Takas sütunu yalnız iki farklı hücrenin gerçekten yer değiştirdiği SWAP'ları (i ≠ min) sayar. Rastgele satır, rand() % 100 ile üretilen yüz öğeli bir örnek diziden alınmıştır; başka bir rastgele dizide takas sayıları biraz değişir, karşılaştırma sayıları değişmez.

Hatalı sürüm her turda n karşılaştırma yapar ve n tur döner: toplam n². Bu, seçimli sıralamanın n(n − 1)/2 karşılaştırmasının iki katından fazladır. Asıl fark takaslardadır. Azalan 500 öğeli dizide hatalı sürüm 124 750 takas yapar; seçimli sıralama yalnız 250. Azalan dizide seçimli sıralamanın her takası iki öğeyi birden son yerine koyar. Örneğin ilk takas 1 ile 500'ü yer değiştirir. Bu yüzden 250 takas yeterlidir. Bu girdide hatalı sürümün takas sayısı da ters sıradaki öğe çiftlerinin sayısına, yani 500 · 499 / 2 = 124 750'ye eşit çıkar.

Bu örnek önemli bir dersi gösterir: bir programın doğru sonuç vermesi, istenen algoritmayı gerçeklediğini göstermez. Algoritma analizi, sonucun yanında o sonuca ulaşmanın maliyetini de sorar. Doğru sürüm, yani j = i + 1'den başlayan ve takası iç döngüden sonra yapan sürüm, bu bölümde kullanılan sürümdür.

1.5.6SWAP: makro mu, fonksiyon mu?

İki değişkenin değerlerini yer değiştirme işlemine takas (swap) denir. Takas C'de iki biçimde yazılabilir. Birincisi, programda kullanılan makrodur:

#define SWAP(x, y, t) \
        ((t) = (x), (x) = (y), (y) = (t))

int temp;
SWAP(list[i], list[min], temp);

Satır sonundaki ters bölü (\), makro tanımının bir sonraki satırda sürdüğünü önişlemciye bildirir. Makronun yararı, bir fonksiyon çağrısı maliyeti taşımamasıdır. Önişlemci makro metnini çağrının yerine koyar; çalışma anında bir çağrı, parametre kopyalama ya da dönüş olmaz. Buna karşılık geçici değişken t makroya dışarıdan verilmelidir; bu yüzden sort içinde temp ayrıca tanımlanır.

İkinci yol bir fonksiyondur:

void swap(int *x, int *y) {
  int temp = *x;
  *x = *y;
  *y = temp;
}

swap(&list[i], &list[min]);

Fonksiyonun parametreleri tamsayı değil, tamsayıyı gösteren işaretçidir (int *). C'de parametreler değerle geçirilir: fonksiyon, gönderilen değerin bir kopyasını alır. swap(int x, int y) diye yazılmış bir fonksiyon yalnız kendi kopyalarını takas eder; çağıran taraftaki değişkenler değişmez. Bu yüzden değişkenlerin kendileri değil, adresleri gönderilir: swap(&list[i], &list[min]). Fonksiyonun içinde *x ifadesi, x'in gösterdiği yerdeki değeri verir. * burada içerik işlecidir (dereference). *x = *y ataması da y'nin gösterdiği değeri x'in gösterdiği yere yazar.

Fonksiyonun yararı, derleyicinin tip denetimi yapmasıdır: swap'a int olmayan bir adres verilirse derleyici uyarır. Geçici değişken temp fonksiyonun yerel değişkenidir; çağıranın bir şey tanımlaması gerekmez. Fonksiyonun adı swap olarak küçük harfle verilmiştir. Fonksiyona da SWAP adı verilseydi önişlemci her SWAP( görünümünü makro olarak açmaya çalışır ve iki tanım çakışırdı.

Makronun gizli bir tehlikesi vardır: argümanlarını birden çok kez değerlendirir. SWAP(a[i++], a[j], t) yazıldığında önişlemci şu metni üretir:

((t) = (a[i++]), (a[i++]) = (a[j]), (a[j]) = (t))

i++ iki kez işletilir. a = {10, 20, 30, 40}, i = 0 ve j = 3 ise önce t = a[0] = 10 olur ve i 1'e çıkar. Sonra a[1] = a[3] = 40 yazılır ve i 2'ye çıkar. En sonunda a[3] = 10 olur. Sonuç {10, 40, 30, 10} ve i = 2'dir: hiçbir takas yapılmamış, 20 değeri kaybolmuştur. Aynı çağrı swap(&a[i++], &a[j]) biçiminde fonksiyonla yapılsaydı i++ bir kez işletilir ve a[0] ile a[3] doğru biçimde takas edilirdi. Bu sonuçlar, örnek derlenip çalıştırılarak doğrulanmıştır.

1.5.7swap() bellekte adım adım

İşaretçiyle parametre geçirmenin bellekte nasıl çalıştığını küçük bir programla izleyelim:

void swap(int *x, int *y) {
  int temp = *x;
  *x = *y;
  *y = temp;
}

int main(void) {
  int a = 3, b = 8;
  swap(&a, &b);
  printf("%d %d\n", a, b);
}

Program çalışınca 8 3 yazar. Bu sonuca nasıl ulaşıldığını görmek için belleği adım adım izleyelim. Her fonksiyon çağrısı, çağrı yığını (call stack) üzerinde bir çerçeve (stack frame) açar. Çerçeve, o çağrının parametrelerini ve yerel değişkenlerini tutar; çağrı bitince yok olur.

1. Başlangıç. main'in çerçevesinde a = 3 ve b = 8 vardır (Şekil 1.4a).
2. Çağrı. swap(&a, &b) çağrılınca swap için yeni bir çerçeve açılır. Parametrelere değerler değil adresler kopyalanır: x, a'yı; y, b'yi gösterir. temp henüz bir değer almamıştır (Şekil 1.4b).
3. int temp = *x; x'in gösterdiği yerdeki değer, yani 3 okunur ve temp'e yazılır.
4. *x = *y; y'nin gösterdiği değer (8), x'in gösterdiği yere, yani main'deki a'ya yazılır. Şu an a = 8, b = 8'dir (Şekil 1.5a).
5. *y = temp; temp'teki 3, y'nin gösterdiği b'ye yazılır. Takas main'in kendi değişkenlerinde gerçekleşmiştir (Şekil 1.5b).
6. Dönüş. swap'ın çerçevesi yok olur; x, y ve temp artık yoktur. Ama yaptıkları değişiklik main'in çerçevesinde kalır: a = 8, b = 3 (Şekil 1.5c).

Aynı izleme Tablo 1.5'te değişken değerleriyle verilmiştir. Tabloda adresler örnek olarak a için 1000, b için 1004 seçilmiştir; bir int dört bayt yer kaplar.

1.6Performans analizi

Seçimli sıralamanın karşılaştırma sayısını hesaplarken bir programın maliyetini, onu çalıştırmadan, yalnız koda bakarak bulduk. Bu kesim bu yaklaşımı genelleştirir. Bir programın ne kadar bellek ve zaman gerektirdiği, girdinin büyüklüğüne bağlı bir fonksiyon olarak hesaplanır.

1.6.1Bir programı değerlendirmek

Bir programın iyi olup olmadığına karar vermek için şu sorular sorulur:

1. Programdan isteneni karşılıyor mu?
2. Doğru çalışıyor mu?
3. Nasıl işletileceği ve kullanılacağı, açıklama satırları da dâhil, belgelenmiş mi?
4. Mantıksal sonuç üretmek için fonksiyonları etkili kullanıyor mu?
5. Kod okunabilir mi?
6. Ana ve ikincil belleği etkili kullanıyor mu?
7. İşletim zamanı kabul edilebilir mi?

Son iki soru performans değerlendirmenin konusudur. İlk beşi de en az onlar kadar önemlidir: hızlı ama yanlış sonuç veren, belgesiz ve okunamayan bir program bakımı yapılamadığı için kısa sürede değerini yitirir. Ancak ilk beş sorunun cevabı büyük ölçüde deneyim ve özen işidir. Son iki soru ise sayılarla cevaplanabilir.

Performans değerlendirme iki yolla yapılır.

• Performans analizi (performance analysis) makineden bağımsızdır. Program çalıştırılmaz; zaman ve bellek gereksinimi koda bakılarak tahmin edilir. Sonuç bir karmaşıklık fonksiyonudur.
• Performans ölçümü (performance measurement) makineye bağlıdır. Program belirli bir makinede, belirli bir derleyiciyle çalıştırılır ve gerçek işletim süresi ölçülür.

İki yol birbirini tamamlar. Analiz, bir algoritmanın girdi büyüdükçe nasıl davranacağını önceden söyler. Ölçüm ise bu tahminin gerçek bir makinede tutup tutmadığını gösterir ve analizin göz ardı ettiği sabitleri ortaya çıkarır.

1.6.2Alan karmaşıklığı

Sabit kısım programın kodunu, basit değişkenleri, sabit boyutlu yapıları ve sabitleri kapsar. Bu bellek, girdi ne olursa olsun aynıdır. Değişken kısım ise girdiye bağlı olarak değişen bellektir: boyu girdiye göre ayrılan diziler, özyinelemeli çağrıların açtığı çerçeveler, malloc ile girdiye göre ayrılan bloklar. Girdinin bu kısmı en çok etkileyen özelliği genellikle boyutudur: dizinin öğe sayısı, matrisin satır ve sütun sayısı. Çözümlemede yalnız değişken kısımla ilgilenilir, çünkü programlar arasındaki farkı girdi büyüdükçe o belirler.

float abc(float a, float b, float c) {
  return a + b + b * c
         + (a + b - c) / (a + b) + 4.00;
}
/* yalniz sabit bellek: S_abc(I) = 0 */

Bellek kullanımı konusunda bir alışkanlık baştan kazanılmalıdır: kod, her şey kısıtlıymış gibi yazılmalıdır. Bugünün bilgisayarlarında bellek bol görünür, ama aynı kod bir gömülü sistemde, bir telefonda ya da milyonlarca kaydı aynı anda işleyen bir sunucuda çalışabilir. Bellek nasıl olsa bol diye boşa bellek harcanmaz.

1.6.3sum ve rsum'un belleği

Bir dizinin öğelerini toplayan iki fonksiyonu karşılaştıralım. sum bir döngü, rsum ise özyineleme kullanır:

float sum(float list[], int n) {
  float tempsum = 0;
  int i;
  for (i = 0; i < n; i++)
    tempsum += list[i];
  return tempsum;
}

float rsum(float list[], int n) {
  if (n)
    return rsum(list, n - 1) + list[n - 1];
  return 0;
}

Özyineleme (recursion), bir fonksiyonun kendini daha küçük bir girdiyle çağırmasıdır. rsum(list, n), ilk n öğenin toplamını şöyle tanımlar: n = 0 ise toplam 0'dır; değilse ilk n − 1 öğenin toplamına list[n-1] eklenir. Kendini çağırmadan doğrudan sonuç veren n = 0 durumuna taban durum (base case) denir. Her çağrı n'yi bir azalttığı için zincir sonunda taban duruma ulaşır.

İki fonksiyonun değişken belleğini bulalım.

• sum'a dizinin öğeleri değil, ilk öğesinin adresi gönderilir. C'de bir dizi parametresi aslında bir işaretçidir; float list[] ile float *list parametre olarak aynı anlamdadır. Bu yüzden dizi ne kadar büyük olursa olsun sum yalnız bir adres, bir int ve iki yerel değişken saklar: S_sum(n) = 0. Öğeler değerle kopyalansaydı, örneğin Pascal'daki gibi bir dizi değer parametresi olarak geçirilseydi, S_sum(n) = n olurdu.
• rsum(list, n) toplam n + 1 kez çağrılır: n, n − 1, …, 1, 0 değerleri için birer kez. Her çağrı, yığında bir çerçeve açar ve bu çerçeveler taban duruma ulaşılıncaya kadar birlikte yaşar. Bu yüzden değişken bellek n ile orantılıdır: S_rsum(n) ∝ n.

Şekil 1.6 bir çerçevenin içeriğini gösterir: dizinin adresi (list), n parametresi ve fonksiyon bitince programın nereden devam edeceğini gösteren dönüş adresi. Ders kitabının varsaydığı 16 bitlik bir makinede bu üç değerin her biri 2 bayttır ve bir çerçeve 6 bayt tutar. n = 1000 için 1001 çerçeve, yani en az 6006 bayt gerekir. 64 bitlik bugünkü makinelerde adresler 8 bayttır ve derleyiciler çerçeveye hizalama ve kayıtçı saklama alanı da ekler. Bir çerçeve tipik olarak en az 24 bayttır, çoğu zaman daha fazlası.

Bu farkın pratik bir sonucu vardır. Çağrı yığını için ayrılan bellek sınırlıdır; Windows'ta varsayılan değer 1 MB civarındadır. rsum çok büyük bir n ile çağrılırsa çerçeveler bu sınırı aşar ve program yığın taşması (stack overflow) ile çöker. Bu notu hazırlarken yapılan denemede rsum, n = 100 000 için doğru sonucu verdi, n = 1 000 000 için ise program çöktü. Aynı girdiyle sum sorunsuz çalıştı. Sınırın tam yeri derleyiciye, işletim sistemine ve derleme seçeneklerine göre değişir.

1.6.4Zaman karmaşıklığı ve program adımı

Bir P programının harcadığı zaman T(P), derleme zamanı ile işletim zamanının toplamıdır. Derleme bir kez yapılır ve program sonra defalarca çalıştırılabilir. Bu yüzden ilgilenilen yalnız işletim zamanıdır; bu zaman t_P ile gösterilir.

İşletim zamanı, programın yaptığı her temel işlemin sayısı ile o işlemin süresinin çarpımlarının toplamı olarak yazılabilir:

t_P(n) = c_a·ADD(n) + c_s·SUB(n) + c_l·LDA(n) + c_st·STA(n) + …

Burada ADD(n), n boyutlu bir girdi için yapılan toplama sayısını, c_a ise bir toplamanın süresini gösterir. Çıkarma (SUB), bellekten yükleme (LDA) ve belleğe yazma (STA) için de birer terim vardır. Formül kesindir ama pratikte kullanışsızdır. c sabitleri derleyiciye, işlemciye ve önbelleğin durumuna bağlıdır ve önceden bilinmesi zordur. Bir derleyicinin bir C deyimini kaç makine komutuna çevireceği de belli değildir.

Bu yüzden zaman, makine komutları yerine program adımlarıyla ölçülür.

Tanımın can alıcı noktası “girdinin boyutundan bağımsız” ifadesidir. a = b + c * d; gibi bir atama tek adım sayılır; birkaç makine komutuna dönüşse de süresi n'ye bağlı değildir. Bir döngü ise tek adım sayılamaz, çünkü kaç kez döneceği n'ye bağlıdır. Döngünün her test edilişi bir adım, gövdesindeki her deyimin her işletilişi ayrı adımlardır. Bildirimler (int i; gibi) çalışma anında iş yapmadığı için adım sayılmaz. Fonksiyon başlığı ve kapanan süslü parantez de adım değildir.

Adım sayısı makineden bağımsızdır, ama gerçek süreyle ilişkisini korur: adım sayısı iki katına çıkarsa süre de yaklaşık iki katına çıkar. Bir adımın süresi makineden makineye değişse de bu oran değişmez.

Performansın neden bu kadar önemli olduğunu uç bir örnek gösterir. Bir savaş uçağının bombalama sistemi programlanıyor olsun. Bu program hedefi 3 saniyede bulup bombayı bırakıyor, karşı tarafınki aynı işi 2 saniyede yapıyorsa, savaş baştan kaybedilmiş demektir. Gerçek zamanlı sistemlerde, büyük veri işleyen sunucularda ve oyunlarda bir saniyelik fark, işe yarayan bir programla işe yaramayan bir program arasındaki farktır.

1.6.5Adım sayma: sum()

Bir fonksiyonun adım sayısını bulmanın düzenli bir yolu adım sayma tablosudur. Tabloda her deyim için üç sayı yazılır. s/e (steps per execution), deyimin bir kez işletilmesinin kaç adım olduğudur. Sıklık, deyimin kaç kez işletildiğidir. Toplam ise bu ikisinin çarpımıdır. Fonksiyonun adım sayısı, toplam sütununun toplamıdır. sum fonksiyonunun tablosu Tablo 1.6'da verilmiştir.

Tablonun en dikkat isteyen satırı for satırıdır. Döngü gövdesi n kez işletilir, ama döngü koşulu n + 1 kez test edilir. i = 0, 1, …, n − 1 değerlerinde test doğru çıkar ve gövdeye girilir; bunlar n test eder. i = n olduğunda test bir kez daha yapılır, yanlış çıkar ve döngü biter. Bu son test de bir adımdır. Atama satırı ve return birer kez işletilir. Toplam 1 + (n + 1) + n + 1 = 2n + 3 adımdır.

1.6.6Sayaçla doğrulama

Tablonun doğruluğu, programa bir sayaç eklenerek denetlenebilir. Global bir count değişkeni sıfırdan başlar ve her program adımında bir artırılır:

float sum(float list[], int n) {
  float tempsum = 0; count++;
  int i;
  for (i = 0; i < n; i++) {
    count++;             /* for testi */
    tempsum += list[i]; count++;
  }
  count++;  /* for'un son testi */
  count++;  return tempsum;
}

Sayaç artırımları tablodaki adımların yerine konmuştur: atamadan sonra bir, her döngü testinde bir, her gövde işletiminde bir, döngünün son testinde bir ve return'de bir. Döngü testinin sayacı gövdenin başına konmuştur, çünkü gövdeye her girişten önce bir test yapılmıştır. Döngüden çıkış testini saymak için döngüden sonra ayrıca bir artırım vardır.

list = {3, 1, 4} ve n = 3 için izleme Tablo 1.7'de verilmiştir.

Sonunda count = 9 = 2 · 3 + 3 olur; tablodaki formül doğrulanmıştır. Fonksiyon 3 + 1 + 4 = 8 değerini döndürür. Sayaçlı fonksiyon n = 0, 1, …, 6 için de çalıştırıldı ve her seferinde count değeri 2n + 3'e eşit çıktı.

Sayaçlı kodda dikkat çeken bir ayrıntı vardır: float tempsum = 0; count++; satırından sonra int i; bildirimi gelir. Bir bloğun ortasında bildirim yapmak C89'da yasaktı, C99'dan beri serbesttir. Bu yüzden kod C99 ya da daha yeni bir standartla derlenmelidir.

1.6.7Adım sayma: rsum()

Özyinelemeli bir fonksiyonun adım sayısı biraz farklı bulunur: her deyimin sıklığı, fonksiyonun kaç kez çağrıldığına göre hesaplanır. rsum(list, n) toplam n + 1 kez çağrılır. Adım sayma tablosu Tablo 1.8'de verilmiştir.

if (n) testi her çağrıda bir kez yapılır, yani n + 1 kez. n sıfırdan farklıyken yapılan n çağrıda ikinci satır işletilir: özyinelemeli çağrının sonucu ile bir öğe toplanır ve döndürülür. Bu satır bir adım sayılır; çağrılan fonksiyonun kendi adımları, o çağrının kendi satırlarında ayrıca sayılır. Taban durumda bir kez return 0 işletilir. Toplam (n + 1) + n + 1 = 2n + 2'dir.

Bu sonuç ilk bakışta rsum'u sum'dan (2n + 3) daha hızlı gösterir. Ama adım sayısı burada yanıltıcıdır. Bir adımın süresi girdiden bağımsızdır, ama bütün adımlar aynı sürede işlemez. Bir özyinelemeli çağrı yeni bir çerçeve açmayı, parametreleri kopyalamayı, dönüş adresini saklamayı ve dönüşte çerçeveyi kaldırmayı gerektirir. Bu iş, bir döngü turundaki bir karşılaştırma ve artırmadan çok daha pahalıdır. Gerçek makinede rsum genellikle sum'dan yavaştır ve fazladan bellek harcar.

Adım sayısının asıl söylediği şey başkadır: n büyüdükçe adım sayısının nasıl büyüdüğü. 2n + 3 ile 2n + 2, n ile doğru orantılı büyür; ikisi de doğrusaldır ve ikisi de O(n)'dir. n iki katına çıktığında iki fonksiyonun da süresi yaklaşık iki katına çıkar.

1.6.8rsum() ve çağrı yığını

rsum'a da sayaç eklenebilir:

float rsum(float list[], int n) {
  count++;               /* if testi */
  if (n) {
    count++;             /* toplama + return */
    return rsum(list, n - 1) + list[n - 1];
  }
  count++;
  return 0;
}

rsum(list, 3) çağrısının izlemesi, çağrı yığınının her adımdaki durumuyla birlikte Tablo 1.9'da verilmiştir. Yığın sütununda en sağdaki çağrı, o anda çalışan çağrıdır.

İzlemede iki evre açıkça görülür. İniş evresinde her çağrı if testini yapar, count'u bir kez daha artırır ve hemen yeni bir çağrı açar. Toplama henüz yapılamaz, çünkü toplamın ilk terimi olan özyinelemeli çağrının sonucu henüz bilinmez. Yığın dört çerçeveye kadar büyür. Dönüş evresinde taban durumdan başlayarak her çağrı, aldığı değere kendi öğesini ekleyip bir alttaki çağrıya döner. Toplamalar bu evrede, list[0]'dan başlayarak yapılır. Sayaç dönüş evresinde artmaz, çünkü toplama ve return adımları iniş evresinde sayılmıştır. Son değer count = 8 = 2 · 3 + 2'dir.

1.6.9Matris toplama

İç içe döngülerin adım sayısı da aynı yolla bulunur. İki matrisi toplayan add fonksiyonunun tablosu Tablo 1.10'da görülür. Fonksiyon c[i][j] = a[i][j] + b[i][j] işlemini her hücre için yapar.

Dış döngünün testi, sum'daki gibi, rows + 1 kez yapılır. İç döngü dış döngünün her turunda baştan başlar; her başlayışında testi cols + 1 kez yapılır. Dış döngü rows tur döndüğü için iç döngü testinin toplam sıklığı rows · (cols + 1)'dir. Atama her hücre için bir kez, toplam rows · cols kez işletilir. Hepsi toplanınca:

(rows + 1) + rows · (cols + 1) + rows · cols = 2·rows·cols + 2·rows + 1

Örneğin rows = 2, cols = 4 için 16 + 4 + 1 = 21 adım bulunur. Formül, fonksiyona sayaç eklenerek dört farklı satır ve iki farklı sütun sayısı için denendi; hepsinde sayaç formülle aynı değeri verdi.

Sonucun büyüme hızı O(rows · cols)'dir; kare bir matriste (rows = cols = n) bu O(n²) olur. Formüldeki 2·rows terimi dış döngünün hangi boyutta döndüğüne bağlıdır. Satır sayısı sütun sayısından çok büyükse (rows ≫ cols) döngülerin yerleri değiştirilebilir: dış döngü sütunlarda, iç döngü satırlarda döner. Bu durumda sayım 2·rows·cols + 2·cols + 1 olur ve küçük terim azalır. Baskın terim ise değişmez. Matris çarpımı ise üç iç içe döngü gerektirir ve O(n³)'tür.

1.6.10En iyi, ortalama ve en kötü durum

Şu ana kadar incelenen fonksiyonlarda adım sayısı yalnız girdinin boyutuna bağlıydı: sum her n öğeli dizide 2n + 3 adım atar. Ama birçok algoritmada aynı boyuttaki iki girdi farklı sayıda adım gerektirir. Doğrusal arama (linear search) bunun en basit örneğidir: bir değer, dizinin öğeleriyle baştan sona tek tek karşılaştırılır ve bulununca durulur.

Şekil 1.8'deki {7, 3, 9, 5, 1, 8} dizisinde 7 aranırsa ilk karşılaştırmada bulunur. 8 aranırsa altı karşılaştırma gerekir. 6 aranırsa da altı karşılaştırmadan sonra bulunamadığı anlaşılır. Bu üç duruma ad verilir:

• En iyi durum (best case), aynı boyuttaki girdiler arasında en az adım gerektiren girdinin maliyetidir.
• En kötü durum (worst case), en çok adım gerektiren girdinin maliyetidir.
• Ortalama durum (average case), girdilerin belirli bir olasılık dağılımına göre beklenen maliyettir.

Ortalama değer şöyle bulunur. Aranan değer dizide var olsun ve n konumun her birinde bulunma olasılığı 1/n olsun. Değer k. konumdaysa (1'den sayarak) k karşılaştırma yapılır. Beklenen karşılaştırma sayısı:

(1/n) · (1 + 2 + … + n) = (1/n) · n(n + 1)/2 = (n + 1)/2

Altı öğeli dizide bu 3,5 eder: ortalamada dizinin yarısı taranır. Yarısı da olsa tarama n ile doğru orantılıdır; bu yüzden ortalama durum da Θ(n)'dir. Θ(n) yazımı, adım sayısının n ile aynı hızda büyüdüğünü, yani n'nin iki sabit katı arasında kaldığını anlatır.

Analizde genellikle en kötü durum verilir. Bunun iki nedeni vardır. Birincisi, en kötü durum her girdi için geçerli bir garantidir: algoritma hiçbir girdide bundan fazla adım atmaz. Gerçek zamanlı bir sistemde ya da bir kullanıcının beklediği bir işlemde bu garanti ortalamadan daha değerlidir. İkincisi, ortalama durumu hesaplamak girdinin olasılık dağılımını bilmeyi gerektirir. Bu dağılım çoğu zaman bilinmez; varsayılan dağılım da gerçeğe uymayabilir. En iyi durum ise nadiren işe yarar bilgi verir: neredeyse her algoritma bazı şanslı girdilerde hızlıdır.

1.7Asimptotik gösterim

Adım sayısını tam olarak bulmak her zaman kolay değildir ve çoğu zaman gerekli de değildir. sum'un 2n + 3 adım attığını bilmek güzeldir, ama bu sayının 2n + 3 mü, 3n + 2 mi olduğu pek önemli değildir. Bir adımın gerçek süresi zaten bilinmez; adım sayısındaki sabit çarpanlar bu bilinmezliğin içinde kaybolur. Önemli olan, n büyüdükçe adım sayısının nasıl büyüdüğüdür: doğrusal mı, karesel mi, üstel mi? Bu soruyu sabitlerden ve küçük terimlerden arındırarak cevaplayan dile asimptotik gösterim (asymptotic notation) denir.

1.7.1Büyük O

Tanım iki serbestlik tanır. Birincisi c sabitidir: g(n)'nin kendisi değil, istenen bir sabit katı f(n)'nin üstünde kalmalıdır. Bu serbestlik sabit çarpanları önemsiz kılar. İkincisi n₀ sabitidir: eşitsizlik yalnız yeterince büyük n değerleri için aranır. Küçük n'lerde ne olduğu önemsenmez. Şekil 1.9 bu durumu gösterir: n₀'dan önce f(n) eğrisi c · g(n)'nin üstünde olabilir, ama n₀'dan sonra hep altında kalır.

sum, rsum ve add için bulunan adım sayıları bu gösterimle şöyle yazılır:

• T_sum(n) = 2n + 3 = O(n). n ≥ 3 için 2n + 3 ≤ 3n olduğundan c = 3, n₀ = 3 seçilebilir.
• T_rsum(n) = 2n + 2 = O(n). n ≥ 2 için 2n + 2 ≤ 3n.
• T_add = 2·rows·cols + 2·rows + 1 = O(rows · cols); kare matriste O(n²).

Gösterimdeki “=” işareti alışılmış eşitlik değildir. O(g(n)), g(n)'nin bir sabit katıyla üstten sınırlanan bütün fonksiyonların kümesidir; f(n) = O(g(n)) ifadesi de “f(n) bu kümenin bir elemanıdır” anlamına gelir. Bu yüzden ifade tek yönlü okunur: 2n + 3 = O(n) yazılır, ama O(n) = 2n + 3 yazılmaz. Büyük O bir üst sınırdır; fonksiyonun en fazla ne hızla büyüdüğünü söyler.

Bu derste en çok zaman karmaşıklığı hesaplanır. Bellek de önemlidir, ama çoğu problemde zaman daha kıt kaynaktır: eksik bellek bazen eklenebilir, geçen zaman ise geri gelmez.

1.7.2Örnek: 3n³ + 6n² + 7n

Bulunan c ve n₀ tek seçenek değildir. Örneğin n ≥ 1 için her terim n³'ün bir katıyla sınırlanabilir: f(n) ≤ 3n³ + 6n³ + 7n³ = 16n³. Bu da c = 16, n₀ = 1 verir. Tanım yalnız bazı sabitlerin var olmasını ister; hangilerinin seçildiği önemli değildir. c = 4 için ise n₀ = 7 gerçekten en küçük değerdir: bir betikle denendiğinde n = 6'da f(6) = 906 > 4 · 216 = 864 çıkar.

Sonucun iki pratik okuması vardır.

• Üst sınır. İşletim zamanı f(n) adımla veriliyorsa, n ≥ 7 için program hiçbir zaman 4n³ adımı aşmaz.
• Kübik büyüme. n üç katına çıktığında süre en fazla 3³ = 27 katına çıkar. Bu algoritma 100 sayıyı 2 saniyede sıralıyorsa, 300 sayıyı sıralaması en fazla 2 · 27 = 54 saniye sürer; 6 saniye değil.

Örnekteki yöntem genelleştirilebilir.

Teorem, bir polinomun büyüme hızını en yüksek dereceli teriminin belirlediğini söyler. Bu yüzden 2n + 3, 100n ve n + 10⁶ aynı sınıftadır: hepsi O(n)'dir.

1.7.3Ω ve Θ

Büyük O yalnız bir üst sınır verir ve bu sınır gevşek olabilir. 3n + 2 = O(n²) ifadesi doğrudur: n ≥ 2 için 3n + 2 ≤ 4n ≤ 4n². Hatta 3n + 2 = O(2ⁿ) da doğrudur. Ama bu ifadeler fonksiyon hakkında pek bilgi vermez. Bir fonksiyonun büyüme hızını tam olarak söylemek için alt sınır ve sıkı sınır kavramları da gerekir.

Θ, O ile Ω'nın birleşimidir: f(n) = Θ(g(n)) ancak ve ancak f(n) = O(g(n)) ve f(n) = Ω(g(n)) ise. Θ, fonksiyonun g(n) ile aynı hızda büyüdüğünü söyler.

Asimptotik gösterim kullanılırken mümkün olan en küçük üst sınır yazılır. 3n + 2 = O(n²) doğrudur ama yanıltıcıdır; okuyan, algoritmanın karesel olduğunu sanabilir. Sıkı bir sınır biliniyorsa Θ ile yazılır. Seçimli sıralama, girdi ne olursa olsun n(n − 1)/2 karşılaştırma yapar. n ≥ 2 için n²/4 ≤ n(n − 1)/2 ≤ n²/2 olduğundan seçimli sıralama Θ(n²)'dir. Doğrusal aramada ise en kötü durum Θ(n), en iyi durum Θ(1)'dir; her girdi için geçerli tek bir sınır istenirse O(n) yazılır.

Bu gösterimler, bir problemin istenen sınırdan daha iyi çözülebildiği durumlarda da düşünmeyi kolaylaştırır. Bir sınav sorusu “O(n + m) sürede çözün” diye sorulmuş olsun. Bir öğrenci problemi O(n)'de çözmüş, sonra sorunun sözüne uymak için kodun sonuna m kez dönen boş bir döngü eklemiş. Bu gereksizdir. O(n) süreli bir çözüm zaten O(n + m)'dir, çünkü büyük O bir üst sınırdır. İstenen sınırdan daha iyisi yapılabiliyorsa ne âlâ.

1.7.4Alışılmış karmaşıklıklar

Algoritmaların zaman karmaşıklıkları çoğunlukla birkaç tanıdık sınıftan birine düşer. Tablo 1.13 bu sınıfları, adlarını ve küçük n değerleri için aldıkları değerleri verir. Tabloda lg n, log₂ n anlamındadır.

Her sınıfın tipik bir kaynağı vardır. Sabit süreli bir işlem, dizinin bir öğesine indisle erişmek gibi, girdinin boyutuna bakmaz. Logaritmik süre, problemi her adımda yarıya indiren algoritmalarda görülür; sıralı bir dizide ikili arama bunun örneğidir. Doğrusal süre girdiye bir kez bakan algoritmaların, örneğin sum'un ve doğrusal aramanın süresidir. Log-doğrusal süre iyi sıralama algoritmalarında ortaya çıkar. Karesel süre iki iç içe döngüden, kübik süre üç iç içe döngüden gelir; seçimli sıralama ve matris çarpımı bunlara örnektir. Üstel ve faktöriyel süre ise bütün alt kümeleri ya da bütün sıralanışları deneyen algoritmaların süresidir.

Tablonun küçük n değerleri yanıltıcı olabilir. n = 4'te 2ⁿ = n² = 16'dır; iki fonksiyon aynı görünür. n = 8'de üstel fonksiyon öne geçmiştir: 2ⁿ = 256, n² = 64. n = 32'de fark milyonlarla ifade edilir. Belli bir noktadan sonra üstel ve faktöriyel terimler, polinom terimlerin hepsini ezer.

1.7.5Büyüme grafiği

Aynı fonksiyonların n = 1 ile n = 12 arasındaki grafiği farkı daha da açık gösterir. Şekil 1.11'in üst grafiğinde dikey ölçek 0 ile 150 arasındadır. Bu ölçekte lg n, n ve n lg n birbirinden ayrışır; n² hızla tırmanır ve n = 12'de 144'e ulaşır. n³ ve 2ⁿ ise grafiğin dışına çoktan çıkmıştır.

Alt grafikte ölçek 0 ile 4500 arasına genişletilmiştir. n = 12'de n³ = 1728 ve 2ⁿ = 4096 olur. 2ⁿ, n = 10 civarında n³'ü geçer ve ondan sonra hep önde kalır. n! ise n = 7'de 5040 değeriyle grafikten çıkar; n = 6'da ise yalnız 720'dir. Bu ölçekte n ve n lg n yatay eksenden ayırt edilemez.

1.7.6Saniyede bir milyar komut

Karmaşıklığın gerçek süreye etkisini görmek için saniyede 10⁹ komut işleyen, yani her adımı 1 nanosaniyede yapan bir makine düşünelim. Tablo 1.14, f(n) adım atan bir algoritmanın bu makinede ne kadar süreceğini gösterir. Hesapta 1 yıl 365 gün, 1 ay 30 gün alınmıştır. Tablodaki bütün değerler bir betikle yeniden hesaplanmış ve doğrulanmıştır.

Bir hücrenin nasıl hesaplandığını görmek için n = 40 ve f(n) = 2ⁿ alalım. 2⁴⁰ ≈ 1,1 · 10¹² adım, nanosaniye cinsinden 1,1 · 10¹² ns, yani yaklaşık 1100 saniyedir. Bu da 18,3 dakika eder. n 10 artıp 50 olduğunda adım sayısı 2¹⁰ = 1024 katına çıkar ve süre 13 güne ulaşır. Üstel algoritmalarda girdiye birkaç öğe eklemek süreyi katlar.

Tablodan üç sonuç çıkar. Birincisi, logaritmik ve doğrusal algoritmalar on bin öğede bile mikrosaniyeler içinde biter. İkincisi, polinom algoritmalar arasında da büyük farklar vardır: on bin öğede n² 100 milisaniye, n³ 16,7 dakika, n⁴ ise 3,86 ay sürer. Üçüncüsü, üstel algoritmalar pratikte yalnız çok küçük girdilerde kullanılabilir. n = 100 için 2ⁿ adım 4 · 10¹¹ asır sürer; evrenin yaşı ise yaklaşık 1,4 · 10⁸ asırdır. n = 10 000 için süre yaklaşık 10²⁹⁹² asırdır.

1.7.7Amortize analiz

En kötü durum analizi her işlemi tek başına ele alır. Ama bazı veri yapılarında işlemler bazen pahalı, çoğunlukla ucuzdur. Böyle bir yapıda her işlemin en kötü maliyetini toplamak, toplam maliyeti olduğundan çok büyük gösterir. Amortize analiz (amortized analysis), n işlemlik bir dizinin toplam maliyetini hesaplar ve n'e böler. Sonuç, işlem başına düşen ortalama maliyettir. Bu ortalama bir olasılık varsayımına dayanmaz; her işlem dizisi için geçerli bir garantidir.

Tipik örnek dinamik dizidir (dynamic array). Dinamik dizi belirli bir kapasiteyle başlar ve öğeleri sona ekler. Dizi dolduğunda realloc ile kapasitesi iki katına çıkarılır. realloc, ayrılmış bir bloğu büyütür; yerinde büyütemezse yeni bir blok ayırır ve eski öğeleri oraya kopyalar. Bir eklemenin maliyeti, bir yazma artı varsa kopyalanan öğe sayısıdır.

Genel durumda n eklemede kopyalanan öğe sayısı 1 + 2 + 4 + … + 2^k'dır; burada 2^k < n'dir. Bu geometrik toplam 2^k+1 − 1 < 2n'dir. Yazmalarla birlikte toplam maliyet 3n'den küçüktür. Tek bir ekleme O(n) sürebilir, ama ekleme başına amortize maliyet O(1)'dir. Bu sınır, 1 ile 1000 arasındaki farklı n değerleri için bir betikle de denetlenmiştir; toplam maliyet her seferinde 3n'nin altında kaldı.

Kapasite iki katına çıkarılmak yerine her seferinde sabit bir miktar, örneğin 10 artırılsaydı sonuç çok farklı olurdu. Bu durumda her 10 eklemede bir bütün dizi kopyalanır ve kopya sayısı 10 + 20 + 30 + … ≈ n²/20 olur. Ekleme başına amortize maliyet O(n)'e çıkar. Katlayarak büyüme, dinamik dizilerin ve birçok kütüphane yapısının dayandığı fikirdir.

1.8Sihirli kare

Asimptotik gösterimin pratik önemini çarpıcı biçimde gösteren bir problem sihirli karedir. Aynı problem için biri kaba kuvvetle, biri akıllı bir kuralla çalışan iki yöntem karşılaştırılınca, doğru algoritmanın hiçbir donanım hızlanmasıyla telafi edilemeyecek bir fark yarattığı görülür.

1.8.1Problem

Bu ortak toplam n'ye bağlı olarak hesaplanabilir. 1'den n²'ye kadar sayıların toplamı n²(n² + 1)/2'dir. Bu sayılar n satıra dağılmıştır ve her satırın toplamı eşittir. Bu yüzden bir satırın toplamı:

n²(n² + 1)/2 ÷ n = n(n² + 1)/2

n = 3 için toplam 3 · 10 / 2 = 15, n = 5 için 5 · 26 / 2 = 65, n = 7 için 7 · 50 / 2 = 175'tir. Şekil 1.12 5 × 5 boyutlu bir sihirli kareyi gösterir.

Şekildeki kareyi denetleyelim. İlk satır 15 + 8 + 1 + 24 + 17 = 65, ilk sütun 15 + 16 + 22 + 3 + 9 = 65, ana köşegen 15 + 14 + 13 + 12 + 11 = 65, diğer köşegen 17 + 5 + 13 + 21 + 9 = 65'tir. Kalan satır ve sütunlar da 65 tutar.

1.8.2Kaba kuvvet ve daha hızlı makine

Problemi çözmenin akla gelen ilk yolu kaba kuvvettir (brute force): bütün olası çözümleri tek tek denemek. 1'den n²'ye kadar sayılar n² hücreye (n²)! farklı biçimde dizilebilir. Her diziliş için satır, sütun ve köşegen toplamları denetlenir. 5 × 5 kare için 25! ≈ 1,55 · 10²⁵ diziliş vardır. Saniyede 10⁹ diziliş deneyen bir makine bunların hepsini 1,55 · 10¹⁶ saniyede dener. Bir asır yaklaşık 3,15 · 10⁹ saniye olduğundan bu süre yaklaşık 4,9 milyon asırdır.

Bu hesaba sık yapılan bir itiraz vardır: on kat daha hızlı, örneğin 10 GHz'lik yeni bir bilgisayar bu problemi hemen çözer; algoritmayla uğraşmaya gerek yoktur. Hesap bu itirazı çürütür:

25! / (10¹⁰ · 3,15 · 10⁹) ≈ 4,9 · 10⁵ asır

On kat hızlı makine 4,9 milyon asrı yaklaşık 490 bin asra indirir. Sonuç hâlâ umutsuzdur. Bin kat hızlı bir makine bile süreyi ancak 4900 asra indirir. Karmaşıklığı (n²)! olan bir algoritmada n'yi 5'ten 6'ya çıkarmak ise adım sayısını 36!/25! ≈ 2,4 · 10¹⁶ katına çıkarır; hiçbir donanım ilerlemesi bunu karşılayamaz.

Doğru algoritma ise aynı kareyi yalnız 25 adımda, bir mikrosaniyenin çok altında kurar. Algoritma donanımdan önce gelir: yavaş bir algoritmayı hızlı bir makinede çalıştırmak, hızlı bir algoritmayı yavaş bir makinede çalıştırmaktan neredeyse her zaman daha kötüdür.

1.8.3Coxeter kuralı ve C kodu

n tek sayı olduğunda sihirli kareyi doğrudan kuran basit bir kural vardır. Horowitz ve Sahni bu kuralı Coxeter'e dayandırır; Siyam yöntemi ya da de la Loubère yöntemi adlarıyla da bilinir. Kural şudur:

1. İlk satırın ortasına 1 yazılır.
2. Sonraki sayı için hep sol üst çapraza gidilir: bir satır yukarı, bir sütun sola.
3. Tablonun dışına taşılırsa karşı kenardan dönülür. Yukarı taşan bir hareket en alt satıra, sola taşan bir hareket en sağ sütuna gider. Tablo, kenarları birbirine yapışık bir silindir gibi düşünülür.
4. Sol üst çapraz doluysa oraya gidilmez; bulunulan karenin hemen altına inilir.

Kural her sayıyı tek adımda yerleştirir ve n² adımda biter: zaman karmaşıklığı O(n²)'dir. Tablonun kendisi zaten n² hücre içerdiği için daha hızlı bir algoritma olamaz; her hücreye en az bir kez yazmak gerekir. Bu yüzden kural Θ(n²) süreli ve en iyi olabilecek bir algoritmadır. Kuralın C ile yazılışı şudur:

void sihirli(int n, int k[][MAX]) {
  int i = 0, j = (n - 1) / 2, s, r, c;
  k[i][j] = 1;        /* k sifirlanmis olmali */
  for (s = 2; s <= n * n; s++) {
    r = (i - 1 < 0) ? n - 1 : i - 1; /* yukari */
    c = (j - 1 < 0) ? n - 1 : j - 1; /* sol */
    if (k[r][c]) i = (i + 1) % n; /* in */
    else { i = r; j = c; }
    k[i][j] = s;
  }
}

Kod satır satır şöyle çalışır:

• k[][MAX], satır uzunluğu MAX olan iki boyutlu bir tamsayı dizisidir. C'de iki boyutlu bir dizi parametresinin ikinci boyutu yazılmalıdır, çünkü derleyici k[i][j] adresini i · MAX + j olarak hesaplar. MAX, programda #define ile tanımlanan bir sabittir ve n'den küçük olamaz.
• i = 0, j = (n - 1) / 2 ilk satırın ortasıdır. n = 5 için j = 2. Oraya 1 yazılır. Kod, bütün hücrelerin sıfır olduğunu varsayar; çağıran tarafın diziyi sıfırla başlatması gerekir. Bir hücrenin dolu olup olmadığı, sıfırdan farklı olup olmadığına bakılarak anlaşılır.
• Döngü s = 2'den n²'ye kadar her sayıyı yerleştirir.
• r ve c sol üst çaprazın satır ve sütunudur. i - 1 < 0 ise satır yukarı taşmıştır; r en alt satıra, n - 1'e gider. Sütun için de aynı denetim yapılır. Koşul işleci ? : bu dönüşü tek satırda yazar.
• k[r][c] sıfırdan farklıysa çapraz doludur. Bu durumda bulunulan karenin altına inilir: i = (i + 1) % n. Mod işlemi alt kenardan taşmayı en üst satıra döndürür. j değişmez.
• Çapraz boşsa oraya geçilir: i = r; j = c;. Sonra k[i][j] = s ile sayı yazılır.

Kod derlenip n = 3, 5 ve 7 için çalıştırıldı ve her satır, sütun ve iki köşegenin toplamı bir program parçasıyla denetlendi. Üç karede de toplamlar sırasıyla 15, 65 ve 175 çıktı. 5 × 5 karenin çıktısı Şekil 1.12 ile aynıdır.

1.8.4Kod izleme: n = 3

sihirli(3, k) çağrısını izleyelim. Kare 3 × 3 olduğu için satır ve sütun indisleri 0, 1 ve 2 değerlerini alır. Tablo 1.15 her sayının nereye yerleştiğini ve nedenini verir.

İzlemenin dikkat isteyen iki satırı vardır. s = 4'te sol üst çapraz (0, 1)'dir ve orada 1 vardır; bu yüzden 3'ün altına, (2, 2)'ye inilir. s = 7'de bulunulan kare (0, 0)'dır. Sol üst çapraz hem satırdan hem sütundan taşar ve (2, 2) olur; orada 4 vardır. Bu yüzden (0, 0)'ın altına, (1, 0)'a inilir. s = 10 > 9 olunca döngü biter.

Sonuçta ortaya çıkan kare şudur: ilk satır 6, 1, 8; ikinci satır 7, 5, 3; üçüncü satır 2, 9, 4. Her satırın, her sütunun ve iki köşegenin toplamı 15 = 3 · (9 + 1)/2'dir. Örneğin ana köşegen 6 + 5 + 4 = 15, diğer köşegen 8 + 5 + 2 = 15'tir.

1.9Performans ölçümü

Performans analizi, bir algoritmanın büyüme hızını makineden bağımsız olarak söyler. Ama gerçek bir makinede gerçek bir girdiyle kaç milisaniye süreceğini söylemez. Bunu öğrenmenin yolu programı çalıştırıp süresini ölçmektir. Ölçüm, analizin göz ardı ettiği sabitleri, önbellek etkilerini ve derleyici iyileştirmelerini de içerir. Bu yüzden iki algoritmanın aynı karmaşıklık sınıfında olduğu durumlarda hangisinin daha hızlı olduğunu ancak ölçüm söyler.

1.9.1clock() ve time()

Standart C kütüphanesi, <time.h> başlığında süre ölçmek için iki fonksiyon sunar. Tablo 1.16 ikisinin kullanılışını karşılaştırır.

clock(), programın başlangıcından beri harcanan işlemci zamanını saat vuruşu (clock tick) cinsinden döndürür. Bir saniyedeki vuruş sayısı CLOCKS_PER_SEC sabitiyle verilir. İki ölçüm arasındaki fark bu sabite bölünerek saniyeye çevrilir. Bölmeden önce (double) dönüşümü yapılmalıdır; yoksa iki tamsayının bölümü küsuratı atar ve 0,4 saniye 0 olarak çıkar. clock()'un çözünürlüğü sistemin vuruş aralığıyla sınırlıdır: iki vuruş arasında biten bir iş 0 süre almış görünür.

time() ise duvar saatini, yani takvim zamanını saniye cinsinden verir. difftime iki zaman arasındaki farkı double olarak döndürür. Çözünürlüğü bir saniyedir; dakikalarca süren işler için uygundur, kısa işler için kabadır. time() ayrıca bilgisayarda o sırada çalışan başka programların süresini de içerir.

Eski kitaplarda ve kodlarda CLK_TCK adına rastlanır. Bu ad standart dışıdır ve eski derleyicilerden kalmadır; bugünkü derleyicilerin çoğu onu tanımaz. Standart C'de CLOCKS_PER_SEC kullanılır.

Ölçüm yaparken bir kural daha vardır: çevre birimleriyle yapılan işlemler, yani ekrana yazma, diske yazma ya da yazıcıya gönderme, işlemcinin hızına göre çok yavaştır. Ölçülen bölgede bir printf bırakılırsa ölçülen süre büyük ölçüde printf'in süresi olur; algoritmanın süresi onun gölgesinde kalır. printf'ler ölçülen bölgenin dışında tutulmalıdır.

1.9.2Seçimli sıralamayı ölçmek

Seçimli sıralamanın gerçek süresini farklı boyutlu dizilerde ölçen program şudur:

#include <stdio.h>
#include <time.h>
#define MAX_SIZE 5001
#define ITERATIONS 20
void sort(int list[], int n);   /* secmeli siralama */

int main(void) {
  int i, j, list[MAX_SIZE];
  int sizelist[] = { 0, 100, 300, 600, 900, 1200, 1500, 2000,
    3000, 3100, 3200, 3300, 3400, 3500, 3600, 3700, 3800,
    3900, 4000, 5000 };
  clock_t start, stop;  double ms;
  for (i = 0; i < ITERATIONS; i++) {
    for (j = 0; j < sizelist[i]; j++)
      list[j] = sizelist[i] - j;   /* azalan dizi */
    start = clock();
    sort(list, sizelist[i]);
    stop = clock();
    ms = 1000.0 * (stop - start) / CLOCKS_PER_SEC;
    printf("%4d eleman: %6.1f ms\n", sizelist[i], ms);
  }
  return 0;
}

• sizelist dizisi ölçüm yapılacak 20 boyutu tutar: 0'dan 5000'e. Boyutlar 3000 ile 4000 arasında sık seçilmiştir; böylece komşu boyutların süreleri karşılaştırılabilir.
• Her boyut için dizi list[j] = sizelist[i] - j ile büyükten küçüğe doldurulur. Seçimli sıralamanın karşılaştırma sayısı girdiden bağımsız olduğu için azalan dizi özel bir durum değildir; ama her ölçümün aynı tür girdiyle yapılmasını sağlar.
• İki clock() çağrısının arasında yalnız sort çağrısı vardır. Diziyi doldurmak ve sonucu yazmak ölçülen bölgenin dışındadır.
• ms = 1000.0 * (stop - start) / CLOCKS_PER_SEC süreyi milisaniyeye çevirir. 1000.0 bir double sabittir; bu yüzden bütün ifade double aritmetiğiyle hesaplanır. Eski kodlarda bu satır (int)(1000*(stop-start)/CLK_TCK) biçiminde görülür; tamsayı bölmesi küsuratı atar ve CLK_TCK standart değildir. Bu yüzden 1000.0 ile double aritmetiği daha doğrudur.
• sort'un tanımı programda verilmez; seçimli sıralama fonksiyonu ve SWAP makrosu aynı dosyaya eklenmelidir. MAX_SIZE 5001'dir; en büyük ölçüm boyu olan 5000 öğe sığar.

1.9.3Sonuçlar ve tutarsızlıklar

Programın eski bir makinedeki örnek çıktısı Şekil 1.14'te çizilmiştir. Noktalar ölçülen süreleri, kesikli eğri ise bir c · n² eğrisini gösterir. Genel eğilim analizle uyumludur: süre n² ile büyür. Ama ayrıntıda tuhaflıklar vardır.

• 600 öğeye kadar bütün ölçümler 0 ms çıkmıştır. Sıralama gerçekten zaman almıştır, ama ölçülemeyecek kadar kısa sürmüştür.
• 3000 öğe 110 ms sürmüş, 3100 öğe ise 93 ms. Daha büyük girdi daha kısa sürmüş gibi görünür.
• 3500, 3600 ve 3700 öğenin üçü de 125 ms sürmüştür; aralarında hiç fark yoktur.

Bu tuhaflıkların nedeni clock()'un çözünürlüğüdür. Sayaç ancak bir saat vuruşunda artar. Sıralama iki vuruş arasında başlayıp biterse stop - start = 0 olur. Vuruş aralığı yaklaşık 15,6 ms olan bir sistemde bütün sonuçlar 15–16 ms'nin katlarına yuvarlanır: 93, 110 ve 125 ms, sırasıyla altı, yedi ve sekiz vuruşa karşılık gelir. Gerçek süre bir vuruş kadar sapabilir. Bu yüzden 3000 ile 3100 öğe arasındaki “ters” fark gerçek değildir. Ayrıca işletim sistemi programı ölçüm sırasında kısa süreliğine durdurup başka bir işi çalıştırabilir; bu da tek ölçümleri bozar.

Program bu notun hazırlandığı bugünkü bir makinede de çalıştırıldı. Sonuçlar Tablo 1.17'de seçilmiş boyutlar için verilmiştir. Kod iyileştirmesiz (-O0) derlenmiştir; bu makinede clock()'un çözünürlüğü 1 ms'dir. Süreler makineye, derleyiciye ve derleme seçeneklerine göre değişir.

Makine eskisinden kat kat hızlıdır, ama tuhaflık sürer: 3500 öğe 40 ms, 3600 öğe 37 ms sürmüştür. 1 ms'lik çözünürlük kısa ölçümlerde hâlâ kabadır; tek seferlik ölçümler de işletim sisteminin araya girmesine açıktır. Bu sorunun çözümü her ölçümü çok kez tekrarlamak ve ortalamasını almaktır.

1.9.4Bekçili doğrusal arama

Tekrarlı ölçümü doğrusal arama üzerinde görelim. Arama fonksiyonu küçük bir hile kullanır:

int seqsearch(int list[], int searchnum, int n) {
  int i;
  list[n] = searchnum;          /* bekci */
  for (i = 0; list[i] != searchnum; i++)
    ;
  return (i < n) ? i : -1;
}

Sıradan bir doğrusal aramanın döngüsünde her turda iki test yapılır: i < n (dizinin sonuna gelindi mi?) ve list[i] != searchnum (aranan bulundu mu?). seqsearch ilk testi kaldırır. Aranan değeri dizinin hemen sonuna, list[n]'ye yazar. Bu hücreye bekçi (sentinel) denir. Aranan değer dizide olmasa bile döngü en geç bekçide durur; bu yüzden sınır denetimine gerek kalmaz. Döngü durduğunda i < n ise değer gerçekten dizide bulunmuştur ve indisi döndürülür. i == n ise döngü bekçide durmuştur ve -1 döndürülerek değerin bulunamadığı bildirilir.

Bekçi hilesinin bir bedeli vardır: dizide n öğe için n + 1 yer ayrılmalıdır. Ölçüm programında MAX_SIZE = 5001 seçilmesinin nedeni budur. Bekçi ayrıca diziyi değiştirir; list[n]'deki eski değer kaybolur. Bu yüzden ölçüm programı her boydan sonra bekçiyi siler.

En kötü durumda, yani aranan değer dizide yoksa, seqsearch n + 1 karşılaştırma yapar: n öğe ve bekçi. Zaman O(n)'dir; en iyi durum, aranan ilk hücredeyken, Θ(1)'dir. Bekçi karşılaştırma sayısını değiştirmez, ama her turdaki test sayısını ikiden bire indirir; döngü yaklaşık iki kat hızlanabilir.

1.9.5Kod izleme: seqsearch()

seqsearch(list, 5, 3) çağrısını, list = {4, 8, 2} dizisinde izleyelim. Dizide üç öğe vardır, ama list[3] için de yer ayrılmıştır. 5 aranmaktadır.

1. list[3] = 5: bekçi yerine konur. Döngü artık en geç burada duracaktır (Şekil 1.15a).
2. i = 0: list[0] = 4 ≠ 5, i 1 olur. Tek test yapılır; sınır denetimi yoktur.
3. i = 1: list[1] = 8 ≠ 5, i 2 olur.
4. i = 2: list[2] = 2 ≠ 5, i 3 olur.
5. i = 3: list[3] = 5; döngü durur. Ama bu bulunan değer bekçidir (Şekil 1.15b).
6. i = 3 < n yanlıştır; fonksiyon -1 döndürür: 5 dizide yoktur. Toplam n + 1 = 4 karşılaştırma yapılmıştır.

Aynı dizide 8 aranırsa döngü i = 1'de durur; 1 < 3 olduğu için fonksiyon 1 döndürür. Bu iki çağrı derlenip çalıştırılmış ve sonuçlar -1 ile 1 olarak doğrulanmıştır.

1.9.6Tekrarlı ölçüm

Arama tek başına mikrosaniyeler sürer; tek seferlik bir ölçümle süresi bulunamaz. Ölçüm programı bu yüzden her boy için aramayı çok kez tekrarlar. Programın ölçüm bölümü şudur:

start = clock();
for (j = 0; j < runtimes[i]; j++)
  pos = seqsearch(list, -1, sizelist[i]);
stop = clock();
total = 1000.0 * (stop - start) / CLOCKS_PER_SEC;
ort = 1000.0 * total / runtimes[i];  /* mikro sn */
list[sizelist[i]] = sizelist[i];  /* bekciyi sil */

• Her n için arama runtimes[i] kez tekrarlanır. Tekrar sayısı küçük boylarda büyük (500 000), büyük boylarda küçüktür (5000). Böylece her boyun toplam ölçüm süresi birkaç vuruştan çok daha uzun olur, ama ölçüm de dakikalar sürmez.
• -1 aranır. Dizide yalnız 0 ile n − 1 arası sayılar olduğu için -1 hiç bulunmaz; her arama en kötü durumdadır ve tam n + 1 karşılaştırma yapar.
• total milisaniye cinsinden toplam süredir. ort = 1000.0 * total / runtimes[i], tek bir aramanın ortalama süresini mikrosaniye cinsinden verir: milisaniyeyi 1000 ile çarpmak mikrosaniyeye çevirir.
• Son satır bekçiyi siler: list[n]'ye eski değeri, yani n'yi geri yazar. Dizinin list[j] = j ile doldurulduğu varsayılır.

Şekil 1.16 sonuçları gösterir. Ortalamalar artık 0 değildir ve n ile doğrusal büyür; bu, O(n) beklentisiyle uyumludur. 3000'den sonraki dalgalanmanın nedeni tekrar sayısının azalmasıdır: runtimes küçüldükçe toplam süre de kısalır ve ölçüm yine kabalaşır. Ölçümün yapıldığı makinede saniyede 1000 vuruş vardı; yani bir vuruş 1 ms'dir.

Aynı ölçüm bu notu hazırlarken bugünkü bir makinede de yapıldı. 100 öğede arama başına yaklaşık 0,4 μs, 1000 öğede yaklaşık 3,4 μs, 5000 öğede yaklaşık 18 μs ölçüldü. Değerler makineye göre değişir, ama oranları aynı kalır: n on katına çıkınca süre de yaklaşık on katına çıkar. Kısa işlerin ölçümünde izlenecek yol özetle şudur: iş çok kez tekrarlanır, toplam süre ölçülür ve tekrar sayısına bölünür.

1.10Özyinelemeli yordamlar

rsum fonksiyonu, bir problemin kendisinin daha küçük bir kopyasıyla nasıl çözülebileceğini gösterdi. Aynı yaklaşım matematikte özyinelemeli olarak tanımlanan birçok fonksiyonu doğrudan koda çevirmeyi sağlar. Her özyinelemeli yordamın iki parçası vardır: kendini çağırmadan sonuç veren bir taban durum ve problemi daha küçük bir probleme indirgeyen bir özyineleme adımı.

1.10.1Faktöriyel, Fibonacci ve binom katsayısı

Üç klasik fonksiyonu ele alalım:

• Faktöriyel. n! = n · (n − 1)! ve 0! = 1! = 1. Taban durum n ≤ 1, adım n · fakt(n − 1)'dir.
• Fibonacci dizisi. f₀ = 0, f₁ = 1 ve i > 1 için f_i = f_i−1 + f_i−2. Taban durum n ≤ 1'dir ve sonuç n'nin kendisidir; adım fibo(n − 1) + fibo(n − 2)'dir.
• Binom katsayısı. C(n, m) = n! / (m! · (n − m)!), n öğeden m tanesini seçmenin yollarının sayısıdır. Pascal üçgeninin bağıntısı C(n, m) = C(n − 1, m) + C(n − 1, m − 1)'dir. Taban durum m = 0 ya da m = n'dir; ikisinde de sonuç 1'dir.

Tanımlar C'ye neredeyse kelimesi kelimesine çevrilir:

long fakt(long n) {
  if (n <= 1) return 1;
  return n * fakt(n - 1);
}

long fibo(long n) {
  if (n <= 1) return n;   /* f0 = 0, f1 = 1 */
  return fibo(n - 1) + fibo(n - 2);
}

long komb(int n, int m) {
  if (m == 0 || m == n) return 1;
  return komb(n - 1, m) + komb(n - 1, m - 1);
}

Kodlar derlenip çalıştırıldığında fakt(5) = 120, fakt(10) = 3628800, fibo(10) = 55, komb(5, 2) = 10 ve komb(10, 3) = 120 verdi. fakt(3) çağrısının çalışmasını izleyelim. fakt(3), 3 · fakt(2)'yi hesaplamak ister; fakt(2), 2 · fakt(1)'i hesaplamak ister; fakt(1) taban durumdur ve 1 döndürür. Dönüşte fakt(2) 2 · 1 = 2, fakt(3) de 3 · 2 = 6 döndürür. Yığın, rsum'da olduğu gibi önce büyür, sonra küçülür.

1.10.2Maliyet

fakt(n) kendini n − 1 kez çağırır ve her çağrıda sabit iş yapar. Süresi O(n)'dir; yığın derinliği de n'dir. Aynı iş bir döngüyle de O(n) sürede ama O(1) bellekle yapılabilir.

fibo ve komb ise bu hâlleriyle üstel zaman harcar. Neden açıktır: aynı alt problemler tekrar tekrar çözülür. fibo(5), fibo(4) ile fibo(3)'ü çağırır; fibo(4) de fibo(3)'ü yeniden çağırır. fibo(3) iki kez, fibo(2) üç kez hesaplanır. Toplam çağrı sayısı 2f_n+1 − 1'dir. Sayaçla yapılan denemede fibo(10) 177, fibo(20) 21 891, fibo(30) ise 2 692 537 çağrı yaptı. Her 10 artışta çağrı sayısı yaklaşık 123 katına çıkar. Buna karşılık yığın derinliği yalnız n'dir, çünkü aynı anda yığında en fazla n çerçeve bulunur. Fibonacci sayıları bir döngüyle, son iki değeri tutarak O(n) sürede hesaplanabilir. Tekrarlanan alt problemlerin sonuçlarını saklayarak üstel süreyi doğrusal ya da polinom süreye indirmek, algoritma tasarımının önemli fikirlerinden biridir.

1.11Karmaşıklık özeti

Bu notta incelenen yordamların zaman ve ek bellek gereksinimleri Tablo 1.18'de toplanmıştır.

Tablodaki “ek bellek” sütunu girdinin kendisini saymaz. sort, sum ve add yalnız birkaç yerel değişken kullanır. rsum ve fibo ise çağrı yığınında n ile orantılı yer kaplar. Dinamik dizinin O(n) belleği öğeleri tutan bloğun kendisidir: kapasite öğe sayısının en fazla iki katıdır ve yeniden ayırma sırasında eski ile yeni blok kısa bir süre birlikte bulunur.

1.12Sık yapılan hatalar

1. “Derlendi ve çalıştı, o hâlde doğru” sanmak. Bir program bir örnekte doğru sonuç verebilir, ama boş girdide, tek öğede ya da tekrarlı değerlerde yanlış çalışabilir. Test verisi bütün senaryoları kapsamalıdır. Hatalı sort sürümü de doğru sonuç verdiği hâlde istenen algoritma değildir.
2. Adım sayısını sabitlerle karıştırmak. 2n + 3 ile 100n aynı sınıftadır: ikisi de O(n)'dir. Asimptotik gösterim sabit çarpanları ve küçük terimleri bilerek atar.
3. Gevşek bir üst sınırı en iyi sınır sanmak. 3n + 2 = O(n²) doğrudur ama bilgi vermez. Mümkün olan en küçük g(n) yazılır; sıkı sınır biliniyorsa Θ kullanılır.
4. Kısa bir işi tek sefer clock() ile ölçmek. Sonuç 0 ya da vuruş aralığının bir katı çıkar. İş çok kez tekrarlanmalı ve ortalaması alınmalıdır.
5. Ölçülen bölgede printf bırakmak. Giriş/çıkış süresi algoritmanın süresini gölgeler.
6. Makroya yan etkili argüman vermek. SWAP(a[i++], a[j], t) i'yi iki kez artırır ve bir değeri yok eder.
7. malloc'un sonucunu denetlememek ve ayrılan belleği geri vermemek. İlki boş işaretçi erişimine, ikincisi bellek sızıntısına yol açar.

1.13Özet

• Süreç. Yazılım gereksinim, çözümleme, tasarım, kodlama ve doğrulama aşamalarından geçer. Tasarımda veri nesneleri ADT, işlemler algoritma olarak tanımlanır. Gerçeklemeyi ertelemek daha iyi bir seçim yapmayı sağlar.
• Algoritma. Girdi, çıktı, kesinlik, sonluluk ve etkinlik ölçütlerini sağlayan sonlu komut dizisidir. Sonlanmayan programlar hesaplama yöntemidir.
• Soyutlama. ADT, belirtimi gerçeklemeden ayırır. C'de bunun aracı başlık dosyası ve opak tiptir: kullanıcı yalnız Kesir * tutar, alanlar .c dosyasında gizlidir. Arayüzün sözleşmesi ve sahiplik kuralı açıkça yazılmalıdır.
• Seçimli sıralama. Her turda kalan kısmın en küçüğü başa taşınır. Her girdide n(n − 1)/2 karşılaştırma yapar ve Θ(n²)'dir; takas sayısı en fazla n − 1'dir. Takas, değişkenlerin adresleri gönderilerek bir fonksiyonla ya da bir makroyla yapılır.
• Sayma. Bellek S(P) = c + S_P(I)'dır. Zaman, program adımlarıyla sayılır: sum 2n + 3, rsum 2n + 2, add 2·rows·cols + 2·rows + 1 adım atar. Özyineleme her çağrıda bir çerçeve açar ve bellek harcar.
• Sınıflama. O üst, Ω alt, Θ sıkı sınırdır. Genellikle en kötü durum verilir, çünkü her girdi için bir garantidir. Amortize analiz bir işlem dizisinin toplam maliyetine bakar; katlanarak büyüyen dinamik dizide ekleme amortize O(1)'dir.
• Büyüme. Küçük n yanıltır. 2ⁿ ve n! kısa sürede umutsuzlaşır. Sihirli karede kaba kuvvet milyonlarca asır, Coxeter kuralı mikrosaniyeler sürer: algoritma donanımdan önce gelir.
• Ölçüm. clock() ile ölçülür; kısa işler tekrarlanır ve ortalaması alınır; giriş/çıkış ölçülen bölgenin dışında tutulur. Bekçi, doğrusal aramada her turdaki sınır testini kaldırır.

1.14Kavram listesi

• sistem yaşam döngüsü system life cycle
• aşağıdan yukarı bottom-up
• yukarıdan aşağı top-down
• algoritma algorithm
• soyut veri tipi abstract data type (ADT)
• gerçekleme implementation
• başlık dosyası header file
• eksik tip incomplete type
• opak tip opaque type
• struct (yapı) struct
• typedef (tip adı) typedef
• ok işleci arrow operator (->)
• malloc malloc
• free free
• boş işaretçi null pointer (NULL)
• bellek sızıntısı memory leak
• sarkan işaretçi dangling pointer
• sıralama sorting
• seçimli sıralama selection sort
• takas swap
• makro macro
• önişlemci preprocessor
• içerik işleci dereference (*)
• performans analizi performance analysis
• alan karmaşıklığı space complexity
• zaman karmaşıklığı time complexity
• program adımı program step
• özyineleme recursion
• taban durum base case
• çağrı yığını call stack
• çerçeve stack frame
• yığın taşması stack overflow
• en iyi / ortalama / en kötü durum best / average / worst case
• asimptotik gösterim asymptotic notation
• büyük O Big O
• büyük Omega Big Omega
• büyük Teta Big Theta
• üstel exponential
• amortize analiz amortized analysis
• dinamik dizi dynamic array
• kapasite capacity
• realloc realloc
• sihirli kare magic square
• kaba kuvvet brute force
• doğrusal arama linear (sequential) search
• bekçi sentinel

1.15Kendini Dene

1. for (i = 0; i < n; i++) for (j = i; j < n; j++) x++; parçasında x++ kaç kez işletilir? n = 4 için değer nedir ve parçanın zamanı hangi sınıftadır?

   Cevap

   i. turda iç döngü n − i kez döner. Toplam n + (n − 1) + … + 1 = n(n + 1)/2'dir. n = 4 için 4 · 5 / 2 = 10. Parça Θ(n²)'dir.

2. 5n² + 20n + 50 = O(n²) eşitliğinde c = 6 seçilirse en küçük n₀ kaçtır?

   Cevap

   5n² + 20n + 50 ≤ 6n² eşitsizliği 20n + 50 ≤ n²'ye denktir. n = 22'de 490 > 484, n = 23'te 510 ≤ 529'dur ve bundan sonra hep sağlanır. En küçük n₀ 23'tür. c = 75 seçilirse n₀ = 1 yeter.

3. Bir dizinin en büyük öğesini bulan şu fonksiyonun en kötü ve en iyi durumda kaç program adımı atar? int maks(int a[], int n) { int m = a[0]; int i; for (i = 1; i < n; i++) if (a[i] > m) m = a[i]; return m; }

   Cevap

   Atama 1 adım, for testi n kez, if testi n − 1 kez, return 1 adım. m = a[i] ataması en kötü durumda (dizi artan sıralıysa) n − 1 kez, en iyi durumda (en büyük öğe başta) hiç işletilmez. En kötü durum 3n, en iyi durum 2n + 1 adımdır; ikisi de Θ(n). Sayaçlı sürüm n = 6 için 18 ve 13 verir.

4. Seçimli sıralama {5, 4, 3, 2, 1} dizisinde kaç karşılaştırma ve kaç gerçek takas (i ≠ min) yapar?

   Cevap

   Karşılaştırma sayısı girdiden bağımsızdır: 5 · 4 / 2 = 10. Takaslar: i = 0'da 5 ile 1, i = 1'de 4 ile 2 yer değiştirir; dizi {1, 2, 3, 4, 5} olur. i = 2 ve i = 3'te min = i'dir. Toplam 2 gerçek takas yapılır.

5. Bekçili seqsearch, beş öğeli bir dizide dizide olmayan bir değeri ararken kaç karşılaştırma yapar? Aranan değer indis 2'deyse kaç karşılaştırma yapar?

   Cevap

   Değer yoksa beş öğe ve bekçi ile n + 1 = 6 karşılaştırma yapılır. Değer indis 2'deyse list[0], list[1] ve list[2] ile 3 karşılaştırma yapılır; döngü i = 2'de durur ve 2 < 5 olduğu için 2 döndürülür.

6. Kapasitesi 4 olan boş bir dinamik diziye, her doluşta kapasite ikiye katlanarak 20 öğe ekleniyor. Toplam kaç öğe kopyalanır? Yazmalarla birlikte toplam maliyet nedir?

   Cevap

   5. eklemede 4, 9. eklemede 8, 17. eklemede 16 öğe kopyalanır: toplam 28. Yazmalarla toplam maliyet 28 + 20 = 48'dir; ekleme başına 2,4 işlem düşer ve 3n = 60 sınırının altında kalır.

7. Özyinelemeli fibo(5) çağrısı, ilk çağrı dâhil, toplam kaç kez fibo çağırır? En derin anda yığında kaç fibo çerçevesi bulunur?

   Cevap

   Çağrı sayısı 2f₆ − 1 = 2 · 8 − 1 = 15'tir. Elle de sayılabilir: T(n) = T(n − 1) + T(n − 2) + 1, T(0) = T(1) = 1 bağıntısından T(2) = 3, T(3) = 5, T(4) = 9, T(5) = 15. En derin zincir fibo(5) → fibo(4) → fibo(3) → fibo(2) → fibo(1) olduğu için yığında en fazla 5 çerçeve bulunur.

8. Θ(n²) süreli bir algoritma 1000 öğede 1 saniye sürüyor. 4000 öğede yaklaşık ne kadar sürer? On kat hızlı bir makinede 1 saniyede kaç öğe işlenebilir?

   Cevap

   n dört katına çıkınca süre 4² = 16 katına çıkar: yaklaşık 16 saniye. On kat hızlı makinede 1 saniyede on kat fazla adım atılır; n² on katına çıkarsa n, √10 ≈ 3,16 katına çıkar. Yaklaşık 3160 öğe işlenir. Karesel bir algoritmada makineyi on kat hızlandırmak girdiyi ancak üç kat büyütür.

9. 5 × 5 sihirli karede Coxeter kuralıyla 2 sayısı hangi hücreye yazılır? Neden?

   Cevap

   1, ilk satırın ortasına, (0, 2)'ye yazılır. Sol üst çapraz (−1, 1)'dir; satır yukarı taştığı için en alt satıra döner ve (4, 1) olur. Hücre boştur; 2 oraya yazılır. Şekil 1.12'de alt satırın ikinci hücresinde 2 görülür.

10. main.c içinde Kesir k; k.pay = 3; yazılırsa ne olur? Neden?

    Cevap

    Derleme hatası olur. main.c yalnız kesir.h'yi görür ve orada struct kesir eksik bir tiptir: derleyici boyunu ve alanlarını bilmez. Bu yüzden bu tipte bir değişken tanımlanamaz ve alanlarına erişilemez. Kullanıcı kesirlerle yalnız Kesir * işaretçisi ve arayüzdeki fonksiyonlar aracılığıyla çalışabilir; opak tipin amacı da budur.

1.16İleri okuma

• E. Horowitz, S. Sahni ve S. Anderson-Freed, Fundamentals of Data Structures in C (2. baskı), Bölüm 1: bu notun temelidir; sistem yaşam döngüsünü, ADT'yi, adım sayma tablolarını, asimptotik gösterimi, sihirli kareyi ve performans ölçümünü daha fazla alıştırmayla verir.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (3. baskı), Bölüm 2–3 ve 17: algoritma analizini, O, Ω ve Θ gösterimlerini kesin tanımlar ve ispatlarla, amortize analizi de dinamik tablo örneğiyle ayrıntılı anlatır.
• R. Sedgewick, Algorithms in C: algoritma analizinin ilkelerini C koduyla ve çok sayıda ölçümle anlatır; kuramsal tahminlerin deneylerle nasıl karşılaştırılacağını gösterir.
• B. W. Kernighan ve D. M. Ritchie, The C Programming Language (2. baskı): işaretçiler, yapılar, önişlemci ve standart kütüphane (<stdlib.h>, <time.h>) için başvuru kaynağıdır.

1.17Kaynaklar

1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. baskı, Bölüm 1.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3. baskı: Bölüm 2–3 (analiz, asimptotik gösterim), Bölüm 17 (amortize analiz).
3. B. W. Kernighan, D. M. Ritchie, The C Programming Language, 2. baskı.
4. R. Sedgewick, Algorithms in C.

İlgili sayfalar: Bölüm 1 sunumu · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.