ALGORİTMANIN ETKİNLİK ANALİZİ PDF

BÖLÜM 7 ALGORİTMANIN ETKİNLİK ANALİZİ ANAHTAR KAVRAMLAR Etkinlik Analizi, Zaman Karmaşıklığı, Fonksiyon Büyüme Hızı, En – İyi Durum, En – Kötü Durum, Ortalama Durum, Asimptotik Notasyon ÖĞRENME HEDEFLERİ 1 2...

BÖLÜM 7 ALGORİTMANIN ETKİNLİK ANALİZİ ANAHTAR KAVRAMLAR Etkinlik Analizi, Zaman Karmaşıklığı, Fonksiyon Büyüme Hızı, En – İyi Durum, En – Kötü Durum, Ortalama Durum, Asimptotik Notasyon ÖĞRENME HEDEFLERİ 1 2 3 4 5 Algoritma- Algoritma- Fonksiyon- Asimptotik Asimptotik nın etkinlik nın temel ların büyüme notasyonları notasyonla- analizinin işleminin hızının nasıl bilir rın algorit- nasıl nasıl belirle- belirleneceği- maların uygulanaca- neceğini bilir ni bilir etkinlik ğını bilir analizinde nasıl uygula- nacağını bilir  YEDİNCİ BÖLÜM Algoritmalar için iki tür etkinlik analizi göz önünde bulundurulmaktadır: zaman etkinliğinin analizi (ya da zaman karmaşıklığı) algorit- manın verilen girdi için ne kadar sürede ya da ne kadar adımda istenen çıktıyı ürettiğinin belirlenmesi, alan et- kinliğinin analizi (ya da alan karmaşıklığı) algoritmanın verilen girdi için istenen sonucu üretirken bellekten ne kadarlık kısma ihtiyaç duyduğu şeklinde tanımlanabilir. Etkinlik analizi algoritmanın pratikte uygulanıp uygu- lanamayacağına dair fikir verirken, aynı zamanda aynı problem için geliştirilmiş farklı algoritmaları da kıyasla- yabilmemize imkan sağlamaktadır. Bu bölümde verilen bir algoritmanın etkinlik analizinin nasıl yapıldığı ör- nekler üzerinden detaylıca incelenecektir. 94 ALGORİTMANIN ETKİNLİK ANALİZİ  ALGORİTMANIN ETKİNLİK ANALİZİ 1. ÖLÇÜ BİRİMİNİN BELİRLENMESİ Verilen bir algoritmanın zaman karmaşıklığını tün işlemleri belirlemek ve bu işlemlerin algorit- hesaplarken, yani algoritmanın verilen girdi için ma sonlandırılıncaya kadar kaç defa gerçekleşti- ne kadar sürede ya da ne kadar adımda istenen rildiğini hesaplamak olabilir. Yalnız bu yöntem- çıktıyı ürettiğini ölçerken; ilk yapılması gereken de algoritmanın gerçekleştirdiği bütün işlemleri bu ölçümün hangi birim kullanılarak yapılaca- belirlemek algoritmanın zaman karmaşıklığı he- ğının belirlenmesidir. Bu noktada akla ilk gelen sabı için hem zor hem de gereksiz bir uğraş ola- zaman karmaşıklığını saniye ya da dakika gibi caktır. Onun yerine algoritmanın gerçekleştir- zaman birimleri cinsinden ölçmek olacaktır. Bu- diği ve algoritmanın çalışma süresini doğrudan nun için algoritmayı üzerinde çalıştırabileceği- etkileyen en önemli ve temel işlemi belirlemek miz bir bilgisayar bulmamız ve algoritmayı bu ve algoritma sonlanıncaya kadar bu işlemin kaç bilgisayarda çalıştırabileceğimiz bir programla- defa uygulandığını hesaplamak daha doğru bir ma dilline aktarmamız gerekmektedir. Sonrasın- yaklaşım olacaktır. da verilen bir girdi için algoritmayı çalıştırabilir Şimdi bu yöntem üzerinden sözde kodu Şekil ve bir kronometre yardımıyla algoritmanın kaç 7.1’deki gibi olan ve verilen bir tamsayı dizisinin saniyede istenen çıktıyı ürettiğini belirleyebiliriz. verilen bir tamsayıyı içerip içermediğini bulma- Burada elbette daha iyi donanıma sahip bir bil- ya yarayan algoritmanın zaman karmaşıklığını gisayar ya da programla dili için daha etkin bir hesaplamaya çalışalım. Arama algoritmasında derleyici kullanmak algoritmanın çalışma süresi- for döngüsü içerisinde aranan tamsayının, di- ni kısaltacaktır. Dolayısıyla; bu ölçme yöntemin- zinin sıradaki elemanına eşit olup olmadığını de bilgisayarın sahip olduğu donanımın kalitesi, kontrol etmemize imkan veren ‘tk = x’ kıyasla- algoritmanın hangi programlama diline nasıl ak- ması algoritmanın temel işlemidir. Örneğin [4, 1, tarıldığı ya da programlama dili için hangi der- 6, 3] tamsayı dizisi ve 10 tamsayısı verildiğinde, leyicinin kullanıldığı gibi etkenler algoritmanın algoritma ‘tk = x’ kod parçası yardımıyla sırasıy- çalışma süresini yani zaman karmaşıklığını doğ- la dizinin elemanlarını 10 elemanı ile kıyaslaya- rudan etkilemektedirler. cak ve dizinin elemanları aranan tamsayıya eşit Diğer yandan, geliştirdiğimiz algoritmala- olmadığından ‘0’ değerine dönecektir. Dikkat rı günlük pratikte kullanabilmemiz için uygun edilirse algoritma bu örneklem için 4 kıyaslama programlama dillerine aktarmamız ve belli bir yapacaktır. Diğer yandan girdiyi [7, 21, 6, 5, 12, 8, takım donanım cihazları satın almamız, yani za- 9, 17] tamsayı dizisi ve 11 tamsayısı olarak belir- man ve para harcamamız gerekmektedir. Dolayı- lersek; bu sefer algoritma girdi üzerinde 8 kıyas- sıyla zamanımızı ve paramızı boşa harcamamak lama yapacak ve verilen tamsayı dizisi verilen 11 için, daha henüz kağıt üstündeyken geliştirdiği- tamsayısını içermediğinden yukarıdaki örnekle- miz algoritmaların etkinlik analizinin yapılması me benzer şekilde ‘0’ değerine dönecektir. ve belki de yatırıma değer olup olmadıklarının belirlenmesi gerekmektedir. Ve yukarıda ifade edilenler düşünüldüğünde bu analizin, algorit- maların üzerinde çalıştırılacağı bilgisayarın sahip olduğu donanımın kalitesi, algoritmanın hangi programlama diline nasıl aktarıldığı gibi etken- Algoritmanın etkinlik analizi algoritmaların üze- rinde çalıştırılacağı bilgisayarın sahip olduğu lerden bağımsız bir şekilde yapılması daha doğru donanımın kalitesi, algoritmanın hangi prog- bir yöntem olacaktır. ramlama diline nasıl aktarıldığı gibi etkenlerden Algoritmanın zaman karmaşıklığını ölçerken bağımsız bir şekilde yapılmalıdır. uygulayabileceğimiz bir yöntem de, algoritma- nın istenen çıktıyı üretirken gerçekleştirdiği bü- ALGORİTMANIN ETKİNLİK ANALİZİ 95 YEDİNCİ BÖLÜM Şekil 7.1 Arama Algoritmasının Sözde Kodu Burada da görülebileceği gibi algoritmanın girdi boyutunun belirlenmesi gerekmektedir. performansı ya da çalışma süresi ile algoritma- Örneğin yukarıdaki örnekte olduğu gibi verilen nın girdi boyutu arasında doğrudan bir ilişki bir tamsayı dizisinin verilen bir tamsayıyı içerip vardır. Daha büyük boyutlu dizilerin verilen bir içermediğini belirlerken girdi boyutu ilgili tam- elemanı içerip içermediğini belirlemek küçük sayı dizisinin eleman sayısı iken, verilen iki mat- boyutlu girdilere nazaran daha çok süre alacak- risin çarpımında girdi boyutu ilgili matrislerin tır. Dolayısıyla algoritmanın gerçekleştirdiği satır ve sütün sayıları olmaktadır. Verilen fonk- en temel işlemin algoritma tarafından kaç defa siyonu T(n) notasyonu ile gösterirsek; n eleman- gerçekleştirildiğini hesap eden fonksiyon, algo- lı bir tamsayı dizisinin verilen bir x tamsayısını ritmanın girdi boyutu üzerinde tanımlanacaktır. içerip içermediğini belirleyen ve Şekil 7.1‘de söz- İlgili fonksiyon girdi boyutu üzerinde tanım- de kod ile gösterimi verilen algoritmanın çalışma landığından, etkinlik analizinde öncelikli olarak süresini veren fonksiyon T(n) = n’dir. 2. EN-İYI DURUM, ORTALAMA DURUM VE EN-KÖTÜ DURUM ETKİNLİK ANALİZLERİ Şekil 7.1‘de verilen Arama algoritması yukarıda tek kıyaslamada sonuçlanmakta ve ‘1’ değerine da gösterildiği gibi, [7, 21, 6, 5, 12, 8, 9, 17] tamsayı dönmektedir. Bu durum elde edilebilecek en iyi dizisi ve 11 tamsayısı için 8 kıyaslamada sonuç- zaman karmaşıklığı olduğundan en-iyi durum lanmakta ve ‘0’ değerine dönmektedir. Halbuki etkinlik analizi olarak tanımlanmaktadır. Bu şe- algoritma aynı boyuttaki [12, 20, 13, 4, 11, 14, 9, 3] kilde bir n boyutlu girdi için algoritmanın zaman dizisi ve 12 tamsayısı için tek kıyaslamada sonuç- karmaşıklığı T(n) = 1 olacaktır. lanacak ve ‘1’ değerine dönecektir. Görüleceği Diğer yandan [7, 21, 6, 5, 12, 8, 9, 17] dizisi ve üzere algoritmalar, aynı boyutta olsalar bile fark- 11 tamsayısı örnekleminde de gözlemlendiği lı yapıdaki girdiler için farklı zaman karmaşıklı- üzere; eğer dizi aranan tamsayıyı içermiyorsa, ğına sahip olabilmekte ve farklı sayıda adımda Arama algoritması dizinin sonuna kadar dizinin sonuç üretebilmektedirler. Algoritmanın etkinlik elemanlarını sırayla aranan tamsayı ile kıyas- analizi için bu farklı zaman karmaşıklıklarından lamakta ve n kıyaslama sonucunda ‘0’ değerine hangisi dikkate alınacaktır? Gelin önce Arama dönmektedir. Bu durum bu algoritma için elde algoritması üzerinden, verilen bir algoritma için edilebilecek en kötü zaman karmaşıklığı oldu- bahsi geçen farklı etkinlik analizlerini belirleye- ğundan en-kötü durum etkinlik analizi olarak ta- lim. nımlanmaktadır. Dolayısıyla bu şekilde bir n bo- yutlu girdi için algoritmanın zaman karmaşıklığı [12, 20, 13, 4, 11, 14, 9, 3] dizisi ve 12 tamsa- T(n) = n olacaktır. yısı örnekleminde de gözlemlendiği üzere; eğer dizinin ilk elemanı aranan tamsayıya eşitse, gir- Bir diğer incelenmesi gereken etkinlik anali- di boyutu ne olursa olsun Arama algoritması zi, algoritmanın rastgele bir girdi üzerinde kaç 96 ALGORİTMANIN ETKİNLİK ANALİZİ  ALGORİTMANIN ETKİNLİK ANALİZİ adımda sonuç ürettiğini belirleyen ve algoritma- olacaktır. Eğer girdilerin tamamı aranan sayıyı nın etkinlik analizi ile ilgili genel durumu ifade içeriyorsa ve i = 1…n için aranan sayının dizinin eden ortalama durum etkinlik analizidir. Yalnız i. elemanına eşit olma durumlarının sayıları bir- ortalama durum etkinlik analizinin uygulanabil- birine eşitse; algoritmanın zaman karmaşıklığı mesi için girdilerin farklı durumlarının olasılık farklı durumların zaman karmaşıklıklarının or- dağılımlarının bilinmesi gerekmektedir. Ortala- talaması olacağından, T(n) = (1 + 2 + … + n) / n, yani ma durum analizinin nasıl uygulanacağını yine T(n) = (n + 1) / 2 olacaktır. Arama algoritması üzerinden anlamaya çalışa- Bu analizden anlaşılacağı üzere; her ne kadar lım. Önce farklı durumlar için algoritmanın za- ortalama durum etkinlik analizi algoritmanın man karmaşıklıklarını belirleyelim. Aranan tam- performansı ile ilgili en doğru tespiti yapıyor sayı, dizinin ilk elemanına eşit olduğunda zaman olsa da, bu tür bir etkinlik analizi girdilerin farklı karmaşıklığı T(n) = 1 olduğunu daha önce belir- durumlarının olasılık dağılımlarının bilinmesini lemiştik. Benzer şekilde aranan tamsayı dizinin gerektirmektedir. Böyle bir dağılımı elde etmek ikinci elemanına eşitse algoritma iki kıyaslamada veya farklı girdi durumları için verilen bir olası- sonuçlanacağından, algoritmanın zaman karma- lık dağılımını doğrulamak da zordur. Dolayısıy- şıklığı T(n) = 2 olacaktır. Genelleyecek olursak; i la ortalama durum etkinlik analizini uygulamak = 1…n için, aranan tamsayı dizinin i. elemanına en-kötü ve en-iyi durum etkinlik analizine naza- eşitse T(n) = i olacaktır. Ayrıca dizi aranan sayıyı ran daha çok çaba gerektirmektedir. içermediğinde, algoritmanın zaman karmaşıklı- Diğer yandan; en-iyi durum etkinlik analizi, ğının T(n) = n olduğunu da daha önce belirlemiş- bu durumu oluşturacak girdilerin gelme olasılığı tik. düşük olduğundan algoritmanın performansını Algoritmanın yeterince girdi üstünde denen- değerlendirme noktasında çok da fikir verme- diğini varsayalım ve i = 1…n olmak üzere, bu gir- yecektir. Bununla birlikte, algoritmanın en uzun dilerden yüzde kaçında aranan sayının dizinin i. sürede sonuç ürettiği olası en kötü girdiler üze- elemanına eşit olduğu veya yüzde kaçının aranan rinden etkinlik analizinin yapılması, performans sayıyı içermediği belirlenmiş olsun. Bu durum- açısından en kötü durumda bile algoritmanın da ortalama durum etkinlik analizini uygularsak; nasıl çalıştığını gözlemlemeye imkan sağladığın- örneğin girdilerin tamamı aranan sayıyı içermi- dan, algoritmanın zaman karmaşıklığı için genel- yorsa, algoritmanın zaman karmaşıklığı T(n) = n likle en-kötü durum analizi dikkate alınmaktadır. Algoritmanın en uzun sürede sonuç ürettiği olası en kötü girdiler üzerinden etkinlik analizinin yapıl- ması, performans açısından en kötü durumda bile algoritmanın nasıl çalıştığını gözlemlemeye im- kan sağladığından, algoritmanın zaman karmaşıklığı için genellikle en-kötü durum analizi dikkate alınmaktadır. 3. FONKSİYONLARIN BÜYÜME HIZI Yukarıda da ifade edildiği gibi, algoritmanın per- nunla birlikte girdi boyutu çok küçük olduğunda, formansı ya da çalışma süresi ile algoritmanın çoğu algoritma için algoritmanın zaman karma- girdi boyutu arasında doğrudan bir ilişki vardır. şıklığı da çok küçük olmaktadır. Dolayısıyla veri- Girdi boyutu arttığında algoritmanın çalışma sü- len bir algoritmanın etkinlik analizini yaparken resi de gözle görülür biçimde artmaktadır. Bu- çok küçük boyutlu girdiler kullanmak anlamlı ALGORİTMANIN ETKİNLİK ANALİZİ 97 YEDİNCİ BÖLÜM olmayacaktır. Yine benzer şekilde farklı algorit- Özetleyecek olursak, algoritma etkinlik ana- maları etkinlikleri üzerinden kıyaslarken küçük lizinde önce algoritmanın gerçekleştirdiği temel boyutlu girdiler kullanıyor olmak ta sağlıklı so- işlem ya da işlemler belirlenecek ve sonrasında nuçlar üretmeyecektir. istenen sonucu üretmek için bu işlemlerin algo- ritma tarafından kaç defa uygulandığını hesap Diğer yandan, algoritmaların etkinlik anali- eden T(n) fonksiyonu üretilecektir. Daha sonra ziyle asıl amaçlanan; algoritmaların tam olarak ise, algoritmanın performansı için gösterge sayı- kaç adımda ya da tam olarak ne kadar sürede labilecek T(n) fonksiyonunun büyüme hızı belir- sonuç ürettiğini belirlemek değil, algoritmaların lenecektir. T(n) fonksiyonunun büyüme hızı bize pratikte uygulanıp uygulanamayacağına dair bir algoritmanın pratikte uygulanıp uygulanamıya- fikir elde etmek ya da aynı problem için gelişti- cağına ya da algoritmanın uygulanabilmesi için rilmiş farklı algoritmaları performans açısından gerekli olan yatırıma değip değmeyeceğine dair kıyaslayabilmektir. Bu tespitlerden hareketle; fikir verecektir. Aşağıda küçükten büyüğe sıralı algoritmaların etkinlik analizinde yaptığımız algoritma etkinlik analizinde yaygın olarak kul- aslında, yukarıda tanımlanan ve algoritmanın lanılan fonksiyon büyüme hızları verilmiştir: temel işlemlerinin algoritma tarafından kaç defa gerçekleştirildiğini bulan T(n) fonksiyonu- 1 logn n nlogn n2 n3 2n 3n n! nun, küçük boyutlu girdiler için değil de büyük boyutlu girdiler için ne ürettiğini bulmak, veya Yukarıdaki skalaya göre örneğin verilen bir en genel haliyle girdi boyutu n büyüdükçe T(n) problem için geliştirilmiş iki farklı algoritmanın fonksiyonunun nasıl değiştiğini anlamaya çalış- etkinlik analizi neticesinde T(n) fonksiyonlarının mak, yani T(n) fonksiyonunun büyüme hızını büyüme hızları sırasıyla logn ve n olarak belirlen- belirlemek olacaktır. Örneğin T(n) = 3n3 + 2n2 mişse, birinci algoritmanın büyüme hızı daha dü- + 1 fonksiyonunu göz önünde bulunduralım. n şük olduğundan, uygulamada performans açısın- = 10 için T(10) = 3.1000 + 2.100 + 1 = 3201 ola- dan birinci algoritma tercih edilecektir. Algorit- caktır. Yine benzer şekilde n = 100 için T(100) maların etkinlik analizinde T(n) fonksiyonlarının = 3.1000000 + 2.10000 + 1 = 3020001 olacaktır. büyüme hızları gözetilerek farklı algoritmaları Görüleceği üzere n’nin değeri büyüdükçe fonksi- kıyaslamak ve sıralamak için ya da geliştirilen bir yonun büyümesine en çok katkı yapan terim 3n3 algoritmanın yukarıdaki büyüme hızları skala- terimidir. Hatta bu noktada fonksiyonun büyü- sındaki uygun yerini tespit edebilmek için yaygın mesine katkısı çok az olduğundan terimin kaysa- olarak 3 farklı asimptotik notasyon kullanılmak- yısı 3 göz ardı edilirse, fonksiyonun büyümesine tadır. Bunlar büyük – Oh (O), büyük – Omega en çok katkı yapan n3 terimidir. Dolayısıyla T(n) (W) ve büyük – Theta (Q) notasyonlarıdır. = 3n3 + 2n2 + 1 fonksiyonunun büyüme hızı n3’tür. 4. ASIMPTOTIK NOTASYONLAR Büyük – Oh (O) notasyonu asimptotik üst sınır Diğer yandan, büyük – Omega (W) notasyo- olarak tanımlanmaktadır. Yani O(f(n)), f(n) fonk- nu asimptotik alt sınır olarak tanımlanmaktadır. siyonu ile aynı ya da daha küçük büyüme hızı- Yani W(f(n)), f(n) fonksiyonu ile aynı ya da daha na sahip fonksiyonları içeren bir küme tanımla- büyük büyüme hızına sahip fonksiyonları içeren maktadır. Buna göre; örneğin g(n) = 7n + 2n – 5 2 bir küme tanımlamaktadır. Buna göre; örneğin fonksiyonunun büyüme hızı n olduğundan, g(n) 2 g(n) = 7n2 + 2n – 5 fonksiyonunun büyüme hızı ∈ O(n2)’dir. Yine benzer şekilde, h(n) = 3n + 2 n2 olduğundan, g(n) ∈ W(n2)’dir. Yine benzer şe- fonksiyonunun büyüme hızı n olduğundan ve n kilde, r(n) = 2n4 + n fonksiyonunun büyüme hızı n2’den küçük olduğundan, h(n) ∈ O(n2)’dir. Fakat, n4 olduğundan ve n4 n2’den büyük olduğundan, r(n) = 2n4 + n fonksiyonunun büyüme hızı n4 ol- r(n) ∈ W(n2)’dir. Fakat, h(n) = 3n + 2 fonksiyonu- duğundan ve n n ’den büyük olduğundan, r(n) ∉ 4 2 nun büyüme hızı n olduğundan ve n n2’den kü- O(n2)’dir. çük olduğundan, h(n) ∉ W(n2)’dir. 98 ALGORİTMANIN ETKİNLİK ANALİZİ  ALGORİTMANIN ETKİNLİK ANALİZİ Son olarak, büyük – Theta (Q) notasyonu gibi, O(2n4) kümesinin de bir elemanı olabilmek- asimptotik sıkı sınır olarak tanımlanmaktadır. tedir. Yani g(n) = 3n2 + n + 2 fonksiyonunun bü- Yani Q(f(n)), f(n) fonksiyonu ile tam olarak aynı yük – Oh gösterimi g(n) = O(4n3) olabileceği gibi, büyüme hızına sahip fonksiyonları içeren bir g(n) = O(2n4) de olabilmektedir. Bununla birlik- küme tanımlamaktadır. Buna göre; örneğin g(n) te, g(n) = 3n2 + n + 2 fonksiyonunun en sade ve = 7n2 + 2n – 5 fonksiyonunun büyüme hızı n2 ol- en küçük büyük – Oh gösterimi g(n) = O(n2)’dir. duğundan, g(n) ∈ Q(n2)’dir. Fakat, h(n) = 3n + 2 Dikkat edilirse, fonksiyonun en sade ve en küçük fonksiyonunun büyüme hızı n olduğundan ve n büyük – Oh gösterimi bize fonksiyonun büyüme n ’den farklı olduğundan, h(n) ∉ O(n )’dir. Yine 2 2 hızını vermektedir. benzer şekilde, r(n) = 2n + n fonksiyonunun bü- 4 Şimdi de g(n) = (3n3 + n)(2logn + 1) + 5n4 fonk- yüme hızı n4 olduğundan ve n4 n2’den farklı ol- siyonunun en sade ve en küçük büyük – Oh gös- duğundan, r(n) ∉ O(n2)’dir. terimini bulmaya çalışalım. Burada g(n) fonksi- Asimptotik notasyonlar için g(n) ∈ O(f(n)) (ya yonu, g1(n) = 3n3 + n, g2(n) = 2logn + 1 ve g3(n) = da g(n) ∉ O(f(n))) gösterimi, g(n) = O(f(n)) (ya da 5n4 olmak üzere g(n) = g1(n). g2(n) + g3(n) şeklinde g(n) ≠ O(f(n))) şeklinde de kullanılabilmektedir. yazılabilir. Önce g1(n), g2(n) ve g3(n) fonksiyon- Ayrıca g1(n) = O(f1(n)) ve g2(n) = O(f2(n)) verildi- larının büyük – Oh gösterimlerini bulalım. Gö- ğinde, g1(n) + g2(n) = O(max{f1(n), f2(n)}) olacak- rüleceği üzere, bu fonksiyonların en sade ve en tır. Yine benzer şekilde g1(n) = O(f1(n)) ve g2(n) = küçük büyük – Oh gösterimleri sırasıyla g1(n) = O(f2(n)) verildiğinde, g1(n).g2(n) = O(f1(n).f2(n)) ola- O(n3), g2(n) = O(logn) ve g3(n) = O(n4)’tür. Yuka- caktır. rıda verilen g1(n) + g2(n) = O(max{f1(n), f2(n)}) ve g1(n).g2(n) = O(f1(n).f2(n)) kurallarını kullanırsak Yukarıda da ifade edildiği gibi; O(f(n)) f(n) g(n) fonksiyonundaki g1(n). g2(n) teriminin büyük fonksiyonu ile aynı ya da daha küçük büyüme – Oh gösterimi g1(n). g2(n) = O(n3logn) olacak ve hızına sahip fonksiyonları içeren bir küme ta- dolayısıyla g(n) fonksiyonunun büyük – Oh gös- nımladığından, örneğin g(n) = 3n2 + n + 2 fonk- terimi g(n) = O(n3logn) + O(n4) = O(n4) olacaktır. siyonu O(4n3) kümesinin bir elemanı olabileceği 5. ÖZYİNELEMELİ OLMAYAN ALGORİTMALARIN ETKİNLİK ANALİZİ Burada yukarıda tanımı verilen asimptotik bü- nasıl bulunduğu örnekler üzerinden anlatıla- yük – Oh notasyonu kullanılarak, özyinelemeli caktır. Algoritmaların zaman karmaşıklığı için olmayan algoritmaların zaman karmaşıklığının en-kötü durum etkinlik analizi uygulanacaktır. Şekil 7.2 Buyuk Algoritması Sözde Kodu İlk olarak Şekil 7.2‘de sözde kod ile gösterimi maktadır. Sonra for dögüsü yardımıyla sırasıyla verilen ve verilen bir dizinin en büyük elemanını ikinciden sonuncuya kadar dizinin elemanlarını bulan algoritmayı göz önünde bulunduralım. Al- ‘temp’ ile kıyaslamakta ve ‘temp’in güncel değe- goritma ‘temp’ isimli bir geçici değişken tanımla- rinden daha büyük bir eleman keşfederse ‘temp’ makta ve dizinin ilk elemanını bu değişkene ata- değişkenine bu elemanı atamaktadır. Algoritma ALGORİTMANIN ETKİNLİK ANALİZİ 99 YEDİNCİ BÖLÜM döngünün sonunda ‘temp’ değişkeninin güncel for döngüsünün her adımında hem kıyaslama değerine dönmektedir. Dikkat edilirse algorit- hem de atama işlemini gerçekleştirecektir. for manın gerçekleştirdiği iki temel işlem vardır: döngüsünün n – 1 adımı olduğundan, algoritma kıyaslama (‘ti > temp’) ve eğer ‘temp’in güncel en-kötü durum için döngüde 2(n – 1) işlem ger- değerinden daha büyük bir sayı keşfedilirse ata- çekleştirecektir. Algoritmanın başındaki ‘temp’ ma (‘temp ← ti’). Burada en-kötü durum etkinlik değişkenine başlangıç değerini atamayı da ayrı analizi için göz önünde bulundurulması gereken bir işlem olarak sayarsak T(n) = 2(n – 1) + 1 ola- girdi elemanları küçükten büyüğe sıralı bir dizi- caktır. Hesaplanan T(n) = 2n – 1 fonksiyonunun dir. Çünkü böyle bir girdi için; dizinin bir son- en sade ve en küçük büyük – Oh gösterimi T(n) raki elemanı her zaman için ‘temp’ değişkeninin = O(n)’dir. Dolayısıyla Şekil 7.2‘de verilen algorit- güncel değerinden büyük olacağından, algoritma manın zaman karmaşıklığı O(n)’dir. Şekil 7.3 Adım Algoritmasının Sözde Kodu Şimdi de benzer şekilde Şekil 7.3‘de sözde adımı olduğundan, algoritma atama işlemini dış- kod ile gösterimi verilen algoritmayı göz önünde taki for döngüsünün herbir adımında sırasıyla n, bulunduralım. Algoritma ‘temp’ isimli bir geçici n – 1, n – 2,..., 1 defa gerçekleştirmektedir. Dola- değişken tanımlamakta ve 0 sayısını bu değişke- yısıyla algoritmanın başındaki ‘temp’ değişkeni- ne atamaktadır. Algoritma iç içe for döngüsünün ne başlangıç değerini atamayı da ayrı bir işlem herbir adımında ‘temp ← temp + 1’ değişkeni olarak sayarsak T(n) = n + n – 1 + n – 2 + … + 1 + 1 üzerinden ‘temp’ değerini 1 artırmakta ve çıktı = (n2 + n + 2) / 2 olacaktır. Hesaplanan T(n) = (n2 + olarak ‘temp’ değişkeninin güncel değerine dön- n + 2) / 2 fonksiyonunun en sade ve en küçük bü- mektedir. Burada algoritmanın gerçekleştirdiği yük – Oh gösterimi T(n) = O(n2)’dir. Dolayısıyla temel işlem atama işlemi ‘temp ← temp + 1’dir. Şekil 7.3‘de verilen algoritmanın zaman karma- İçteki for döngüsünün i’den n’ye kadar (n – i + 1) şıklığı O(n2)’dir. Şekil 7.4 Simetrik Algoritmasının Sözde Kodu Son olarak Şekil 7.4‘de sözde kod ile gösteri- temel işlemi kıyaslamadır (‘t[i][k] ≠ t[k][i]’). Dik- mi verilen ve verilen bir matrisin simetrik olup kat edilirse, dıştaki for döngüsünde n adım ol- olmadığını belirleyen algoritmayı göz önünde duğundan, ve döngünün her adımı için içteki bulunduralım. Görüleceği üzere algoritmanın for döngüsünde yine n defa kıyaslama gerçek- 100 ALGORİTMANIN ETKİNLİK ANALİZİ  ALGORİTMANIN ETKİNLİK ANALİZİ leştirildiğinden, algoritma en-kötü durum için n2 fonksiyonunun en sade ve en küçük büyük – n2 kıyaslama gerçekleştirecek ve dolayısıyla T(n) Oh gösterimi T(n) = O(n2)’dir. Dolayısıyla Şekil = n2 olacaktır. Burada en-kötü durum etkinlik 7.4‘de verilen algoritmanın zaman karmaşıklığı analizi için göz önünde bulundurulması gereken O(n2)’dir. girdi simetrik bir matristir. Hesaplanan T(n) = Şekil 7.5 Kuvvet Algoritmasının Sözde Kodu 6. ÖZYINELEMELI ALGORITMALARIN ETKINLIK ANALIZI Burada yukarıda tanımı verilen asimptotik bü- rilmekte ve girdi boyutu bir azaltılarak algoritma yük – Oh notasyonu kullanılarak, özyinelemeli tekrar çalıştırılmaktadır. Algoritmanın zaman algoritmaların zaman karmaşıklığının nasıl bu- karmaşıklığına T(n) dersek, algoritmanın içeri- lunduğu örnekler üzerinden anlatılacaktır. Öz- sindeki özyineleme çağrısının (yani ‘X.Kuvvet(X, yinelemeli algoritmalar için de, özyinelemeli N – 1)’ komutunun) zaman karmaşıklığı T(n – 1) olmayan algoritmaların etkinlik analizindekine olacağından, T(n) = T(n – 1) + 1 olacaktır. Girdi benzer olarak; önce algoritmanın temel işlemleri boyutu N = 0 olduğunda, algoritma tek işlem belirlenecek ve algoritmanın bu temel işlemleri gerçekleştirerek 0 değerine döneceğinden T(0) kaç defa uyguladığını hesaplayan T(n) fonksiyo- = 1’dir. Şimdi T(0) = 1 başlangıç koşulunu göz nu üretilecektir. Yalnız özyinelemeli algoritma- önünde bulundurarak T(n) = T(n – 1) + 1 bağın- lar için T(n) fonksiyonunu üretmek kolay olma- tısını çözelim. Burada bağıntıyı çözmekten kasıt, maktadır. Önce T(n) fonksiyonu için özyineleme eşitliğin sağ tarafının belli bir takım yöntemler bağıntısının belirlenmesi ve sonrasında bu ba- kullanarak T fonksiyonuna bağımlılığını ortadan ğıntının çözülmesi gerekmektedir. T(n) fonksi- kaldırmak ve eşitliğin sağında sadece n değişke- yonu için özyineleme bağıntısı belirlendikten ve ninden oluşan ifadeler elde etmektir. çözüldükten sonra, algoritmanın zaman karma- şıklığı için yine yukarıdaki analizlere benzer T(n) fonksiyonunun en sade ve en küçük büyük – Oh T(n) = T(n – 1) + 1 (1) gösterimi bulunacaktır. ifadesinde n gördüğümüz yere n – 1 yazarsak T(n İlk olarak Şekil 7.5‘de sözde kod ile gösterimi – 1)’in karşılığı T(n – 1) = T(n – 2) + 1 bulunacaktır. verilen ve verilen bir X tamsayısının N. kuvvetini Bunu ilk bağıntıda eşitliğin sağındaki T(n – 1)’in bulan özyinelemeli algoritmayı göz önünde bu- yerine yazarsak, lunduralım. Algoritma ‘N = 0’ koşulu sağlanırsa 1 sayısına dönmekte, aksi halde ‘X.Kuvvet(X, N – 1)’ komutuyla girdi boyutu 1 azaltılarak algoritma T(n) = T(n – 1) + 1 = T(n – 2) + 1 + 1 (2) tekrar çalıştırılmaktadır. Algoritmanın gerçekleş- tirdiği temel işlemi kıyaslama olarak belirtirsek, elde etmiş oluruz. Yine benzer şekilde (1) eşitli- algoritma içerisinde bir temel işlem gerçekleşti- ğinde n gördüğümüz yere n – 2 yazarsak T(n – ALGORİTMANIN ETKİNLİK ANALİZİ 101 YEDİNCİ BÖLÜM 2)’in karşılığı T(n – 2) = T(n – 3) + 1 bulunacaktır. elde etmiş oluruz. Bu şekilde devam edilirse i. Bunu (2) bağıntısında eşitliğin sağındaki T(n – adımda 2)’in yerine yazarsak, T(n) = T(n – i) + i.1 (4) T(n) = T(n – 2) + 1 + 1 = T(n – 3) + 1 + 1 + 1 (3) Özyinelemi algoritmaların etkinlik analizinde, önce temel işlemlerin algoritma tarafından kaç defa gerçekleştirildiğini hesap eden T(n) fonksiyonu için özyineleme bağıntısı belirlenmeli ve sonrasında zaman karmaşıklığı için bu bağıntı çözülmelidir. ifadesi elde edilecektir. Burada i = n için (4) eşit- en küçük büyük – Oh gösterimi T(n) = O(n)’dir. liğinde T(n) = T(0) + n elde edilecektir. T(0) = 1 Dolayısıyla Şekil 7.5‘de verilen algoritmanın za- olduğundan, (4) eşitliği T(n) = n + 1 olacaktır. He- man karmaşıklığı O(n)’dir. saplanan T(n) = n + 1 fonksiyonunun en sade ve Şekil 7.6 EnBuyuk Algoritmasının Sözde Kodu Şimdi de Şekil 7.6‘da sözde kod ile gösterimi kıyaslamasını da algoritmanın gerçekleştirdiği verilen ve verilen bir tamsayı dizisinin en bü- temel işlemlerden sayarsak, algoritma içerisin- yük elemanını bulan özyinelemeli algoritmayı de 3 temel işlem gerçekleştirilmektedir. Ayrıca göz önünde bulunduralım. ‘i = j’ koşulu sağla- ‘EnBuyuk([ti,…,tmid])’ ve ‘EnBuyuk([tmid+1,…,tj])’ ko- nırsa algoritma ti sayısına dönmekte, aksi halde mutlarıyla algoritma iki defa daha çalıştırılmak- ‘EnBuyuk([ti,…,tmid])’ ve ‘EnBuyuk([tmid+1,…,tj])’ ko- tadır. Algoritmanın zaman karmaşıklığına T(n) mutlarıyla girdi boyutu yarıya indirilerek algo- dersek, algoritmanın içerisindeki özyineleme ritma tekrar çalıştırılmaktadır. Dikkat edilirse çağrılarının (yani ‘EnBuyuk([ti,…,tmid])’ ve ‘EnBu- ‘mid ← (i + j)/2’ atamasını ve ‘buyuk1 < buyuk2’ yuk([tmid+1,…,tj])’ komutlarının) zaman karmaşıklı- 102 ALGORİTMANIN ETKİNLİK ANALİZİ  ALGORİTMANIN ETKİNLİK ANALİZİ ğı T(n/2) olacağından, T(n) = 2T(n/2) + 3 olacak- T(n) = 4(2T(n/8) + 3) + 3(1 + 2) = 8T(n/8) + 3(1 + 2 tır. Girdi boyutu N = 1 olduğunda, algoritma tek + 4) (9) işlem gerçekleştirerek ‘ti’ değerine döneceğinden T(1) = 1’dir. Şimdi T(1) = 1 başlangıç koşulunu göz önünde bulundurarak T(n) = 2T(n/2) + 3 bağıntı- elde etmiş oluruz. Bu şekilde devam edilirse i. sını çözelim.Yukarıda çözüme benzer şekilde, adımda T(n) = 2T(n/2) + 3 (7) T(n) = 2i T(n/2i) + 3(1 + 2 + … + 2i-1) (10) ifadesinde n gördüğümüz yere n/2 yazarsak T(n/2)’nin karşılığı T(n/2) = 2T(n/4) + 3 bulu- ifadesi elde edilecektir. Burada i = logn için T(n) nacaktır. Bunu ilk bağıntıda eşitliğin sağındaki = 2lognT(1) + 3(1 + 2 + … + 2logn - 1 olacaktır. Eşitliğin T(n/2)’nin yerine yazarsak, sağını düzenlersek, T(1) = 1 olduğundan T(n) = 4n olacaktır. Hesaplanan T(n) = 4n fonksiyonunun en sade ve en küçük büyük – Oh gösterimi T(n) T(n) = 2T(n/2) + 3 = 2(2T(n/4) + 3) + 3 = 4T(n/4) + = O(n)’dir. Dolayısıyla Şekil 7.6‘da verilen algorit- 3(1 + 2) (8) manın zaman karmaşıklığı O(n)’dir. elde etmiş oluruz. Yine benzer şekilde (7) ifade- sinde n gördüğümüz yere n/4 yazarsak T(n/4)’ün karşılığı T(n/4) = 2T(n/8) + 3 bulunacaktır. Bunu (8) bağıntısında eşitliğin sağındaki T(n/4)’ün ye- rine yazarsak, ALGORİTMANIN ETKİNLİK ANALİZİ 103 YEDİNCİ BÖLÜM BÖLÜM ÖZETİ Bu bölümde algoritmanın verilen girdi için ne kadar sürede ya da ne kadar adımda istenen çıktıyı üret- tiğinin belirlenmesi olarak tanımlayabileceğimiz algoritmanın zaman karmaşıklığının nasıl hesaplan- dığı örnekler üzerinden detaylıca incelenmiştir. Bir algoritmanın verilen girdi için ne kadar sürede ya da ne kadar adımda istenen çıktıyı ürettiğini ölçerken; ilk yapılması gereken bu ölçümün hangi birim kullanılarak yapılacağının belirlenmesidir. Her ne kadar akla ilk gelen zaman karmaşıklığını saniye ya da dakika gibi zaman birimleri cinsinden ölçmek olsa da, bu noktada bilgisayarın sahip olduğu donanımın kalitesi, algoritmanın hangi program- lama diline nasıl aktarıldığı ya da programlama dili için hangi derleyicinin kullanıldığı gibi etkenler algoritmanın çalışma süresini yani zaman karmaşıklığını doğrudan etkilemektedirler. Algoritmaların zaman karmaşıklığını daha sağlıklı bir şekilde hesaplayabilmek için etkinlik analizinin, algoritmaların üzerinde çalıştırılacağı bilgisayarın sahip olduğu donanımın kalitesi, algoritmanın hangi programlama diline nasıl aktarıldığı gibi etkenlerden bağımsız bir şekilde yapılması daha doğru bir yöntem olacaktır. Algoritmanın zaman karmaşıklığını ölçerken uygulayabileceğimiz yöntem, algoritmanın istenen çıktıyı üretirken gerçekleştirdiği temel işlemleri belirlemek ve bu işlemlerin algoritma sonlandırılın- caya kadar kaç defa gerçekleştirildiğini hesaplayan bir T(n) fonksiyonu tanımlamak olacaktır. Bu fonk- siyon algoritmanın girdi boyutu üzerinde çalışacaktır. Sonrasında, algoritmanın performansı için gös- terge sayılabilecek T(n) fonksiyonunun büyüme hızı belirlenecektir. T(n) fonksiyonunun büyüme hızı bize algoritmanın pratikte uygulanıp uygulanamıyacağına ya da algoritmanın uygulanabilmesi için gerekli olan yatırıma değip değmeyeceğine dair fikir verecektir. Bu bölümde ayrıca etkinlik analizinde T(n) fonksiyonlarının büyüme hızları gözetilerek farklı algo- ritmaları kıyaslamak ve sıralamak için ya da geliştirilen bir algoritmanın büyüme hızları skalasındaki uygun yerini tespit edebilmek için yaygın olarak kullanılan büyük – Oh (Ο), büyük – Omega (Ω) ve bü- yük – Theta (Θ) asimptotik notasyonları incelenmiştir. Diğer yandan asimptotik büyük – Oh notasyo- nu kullanılarak, özyinelemeli ya da özyinelemeli olmayan algoritmaların zaman karmaşıklığının nasıl bulunduğu da örnekler üzerinden anlatılmıştır. 104 ALGORİTMANIN ETKİNLİK ANALİZİ  ALGORİTMANIN ETKİNLİK ANALİZİ GÖZDEN GEÇİRELİM 1. Toplam([t1,…, tn]) 3. Büyük – Omega (Ω) notasyonu asimp- temp ← 0 totik alt sınır olarak tanımlanmaktadır. for (k = 1 to n){ Buna göre f(n) = 2n3+1 fonksiyonu için temp ← temp + tk} aşağıdakilerden hangisi doğru değildir? return temp a) f(n) = Ω(logn) b) f(n) = Ω(n) T(n) fonksiyonu algoritmanın temel iş- lemi ya da işlemlerinin algoritma tara- c) f(n) = Ω(n2) fından kaç defa gerçekleştirildiğini sa- d) f(n) = Ω(n3) yan fonksiyon olarak tanımlanmaktadır. e) f(n) = Ω(n4) Buna göre yukarıda sözde kod ile göste- rimi verilen algoritmanın T(n) fonksiyo- nunun kuralı aşağıdakilerden hangisin- de doğru olarak verilmiştir? a) T(n) = 2n2 + 2 b) T(n) = n2 + 2 c) T(n) = 2n + 1 4. Büyük – Theta (Θ) notasyonu asimptotik d) T(n) = n – 3 sıkı sınır olarak tanımlanmaktadır. Buna e) T(n) = logn + 3 göre f(n) = n2+3 fonksiyonu için aşağıda- kilerden hangisi doğrudur? a) f(n) = Θ(logn) 2. İkiliArama(A,i,k,x) if (i >= k) b) f(n) = Θ(n) return false c) f(n) = Θ(n2) mid ← (i+ k)/2 d) f(n) = Θ(n3) if (A[mid] = x) e) f(n) = Θ(n4) return true elseif (A[mid] > x) return İkiliArama(A,i,mid-1,x) else return İkiliArama(A,mid+1,k,x) Yukarıda sözde kod ile gösterimi verilen özyinelemeli algoritmanın zaman kar- 5. Büyük – Oh (Ο) notasyonu asimptotik maşıklığının özyineleme bağıntısı aşa- üst sınır olarak tanımlanmaktadır. Buna ğıdakilerden hangisinde doğru olarak göre f(n) = 2n3+1 fonksiyonu için aşağıda- verilmiştir? kilerden hangisi doğru değildir? a) T(n) = T(n/2) + n a) f(n) = O(n) b) T(n) = T(n/2) + 4 b) f(n) = O(n3) c) T(n) = 2T(n/2) + 1 c) f(n) = O(n3logn) d) T(n) = 3T(n/2) + 2 d) f(n) = O(n4) e) T(n) = 4T(n/2) + 3 e) f(n) = O(n5) ALGORİTMANIN ETKİNLİK ANALİZİ 105 YEDİNCİ BÖLÜM 6. Kuvvet(X,n) 8. EnBuyuk([t1,…, tn]) temp ← 1 temp ← t1 for ( k = 1 to n){ for ( k = 2 to n){ temp ← temp.x} if (tk > temp){ return temp temp ← tk}} return temp Yukarıda sözde kod ile gösterimi verilen algoritmanın zaman karmaşıklığı aşağı- Yukarıda sözde kod ile gösterimi verilen dakilerden hangisinde doğru olarak ve- EnBuyuk algoritmasının farklı eleman- rilmiştir? lardan oluşan bir sayı dizisini girdi ola- a) O(logn) rak aldığı kabul edilirse en-iyi durum zaman karmaşıklığını verecek olan girdi b) O(n) aşağıdakilerden hangisidir? c) O(nlogn) a) Girdinin ilk elemanının en büyük ele- d) O(n2) man olması e) O(n )3 b) Girdinin son elemanının en büyük eleman olması c) Girdinin küçükten büyüğe sıralı ele- manlardan oluşması d) Girdinin ortanca elemanının en bü- yük eleman olması e) Girdinin ilk yarısının küçükten büyü- ğe ikinci yarısının büyükten küçüğe elemanlardan oluşması 7. Toplam([t1,…, tn]) temp1 ← 0 for ( i = 1 to n){ for ( j = 1 to n){ temp2 ← 0 for ( k = 1 to n){ temp2 ← temp2 + k temp1 ← i.temp1 – j.temp2}}} return temp1 9. Büyük – Oh (Ο) notasyonu asimptotik Yukarıda sözde kod ile gösterimi verilen üst sınır olarak tanımlanmaktadır. Buna algoritmanın zaman karmaşıklığı aşağı- göre f(n) = n7+3 fonksiyonu için aşağıda- dakilerden hangisinde doğru olarak ve- kilerden hangisi doğrudur? rilmiştir? a) f(n) = O(n) a) O(logn) b) f(n) = O(n2) b) O(n) c) f(n) = O(n4) c) O(nlogn) d) f(n) = O(n6) d) O(n2) e) f(n) = O(n8) e) O(n3) 106 ALGORİTMANIN ETKİNLİK ANALİZİ  ALGORİTMANIN ETKİNLİK ANALİZİ 10. Büyük – Omega (Ω) notasyonu asimp- totik alt sınır olarak tanımlanmaktadır. Buna göre f(n) = n2+3 fonksiyonu için aşağıdakilerden hangisi doğrudur? a) f(n) = Ω(n) b) f(n) = Ω(n3) c) f(n) = Ω(n5) d) f(n) = Ω(n7) e) f(n) = Ω(n9) Yanıt Anahtarı: 1-C 2-B 3-E 4-C 5-A 6-B 7-E 8-A 9-E 10-A Kaynakça Levitin A. (2012) Introduction to The Design & Analysis of Algorithms, 3rd Edition, Pearson. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. (2009) Introduction to Algorithms, 3rd Edition, MIT Press. ALGORİTMANIN ETKİNLİK ANALİZİ 107