Algoritma Analizi ve Asimtotik Karmaşıklık
İlk paylaşımım olarak Algoritma Analizi ve Asimtotik Karmaşıklık konularını ele aldım. Bu konuları açıklarken hem meraklısına detaya inerek açıklamaya çalıştım hem de basit bir anlatım ile aradığınızı bu makale içerisinde bulmanıza olanak sağladım. Keyifli okumalar.
Algoritma Analizi Nedir ?
Bir bilgisayar programının performansı ve kaynak kullanımı konusundaki teorik çalışmalardır. Diğer bir deyişle, algoritmanın icra edilmesi sırasında duyulacağı kaynak miktarının tahmin edilmesine denir.
Bu kaynaklar arasında bir çok şey akla gelebilir. Bellek, ileti bant genişliği, mantık kapıları… Fakat en mühim olanı bizim için zamanın tahmin edilmesidir.
Programımızın alacağı zamanı tahmin etmek, kesin bir ifade ile ( 20 dakika, 3 saat…) dile getirmek olanaksızdır. Bunun nedeni o algoritmanın alacağı süre icra ettiği makineden makineye değişkenlik gösterecektir. Örneğin A bilgisayarında 20.566 milisaniye(ms) alan bir algoritma, B bilgisayarında 25.333 milisaniye(ms) süre alabilir.
Bizim asıl hesaplayacağımız nokta bu algoritmaların süresinin niceliksel olarak değil, daha çok teorik ve yaklaşık olarak bir notasyonda göstermeye dayanmaktadır.
Çalışma Zamanının Ölçülmesinde Yanlış Bilinenler
- Saniye, milisaniye cinsinden ölçülmez.
- Belirli bir bilgisayarın veya derleyicinin hızına bağlı olarak ölçülemez.
Çalışma Zamanının Ölçülmesinde Temel İşlem
Algoritma içinde çalışma zamanına en çok etki eden işlem seçilir. Bu işlemlerin kaç kere çalıştığı ölçülmelidir. Bu zaman ve giriş boyutu arasındaki kavrama ise Asimtotik Karmaşıklık(Asymptotic Complexity) denir.
Karmaşıklık konusuna birazdan geleceğiz, öncelikle çalışma zamanı ile ilgili bir kaç detaya bakalım.
’n’ boyutlu bir problemin algoritmasını çalıştırmak için gerekli zaman olarak bu formülü açıklayabiliriz. Ancak burada vurgulamak istediğim bir nokta; çalışma süresi olarak bahsedilen tanımın, matematiksel olarak “tilde yaklaşımı” ile ifade edilmiş olacağıdır.
Tilde Yaklaşımı : Karmaşık ve uzun matematiksel ifadelerin önemsiz kısımlarını ihmal etmek ve matematik formüllerini sadeleştirmek için tilde gösterimi (~) adı verilen matematik aracı kullanılır. Bu notasyon tilde yaklaşımı ile çalışmamızı sağlar.
Peki bu “tilde yaklaşımı” ve “çalışma zamanı” nedir ve ne için öğrendik ? ne zaman kullanacağız? gibi aklınızda soru işaretleri oluştuysa aşağıdaki örneği incelediğinizde anlayacaksınız.
Basit bir döngü ile başlayalım. Diğer örneklerde zorlaştıracağım.
* Basit bir örnek. Ancak açıklamak için güzel bir başlangıç. Öncelikle Maliyet ve Tekrar sütunlarına dikkat edin. Maliyet’in Cop ve Tekrar’ın C(n) olduğunu hatırlatmakta fayda var. Formüle bakacak olursanız bunların toplam çarpımı bize çalışma zamanını vermekte.
** Tilde notasyonuna gelecek olursak, en alt kısımda görüleceği üzere tüm maliyet ve tekrarlar çarpılıp toplandı. Bunların önemli kısımları(yani n değerleri, giriş verisi) sonuç olarak yazıldı. Devamında T(n) değerinin sadece önemli kısmını (~n yani doğrusal) almalıyız.
Peki önemli kısmını neye göre seçmeliyiz ?
diye soracak olursanız 2 cevap vereceğim.
- Birincisi olabildiğince en sade halini alacağız. Değerini katlamalı olarak küçültmeden(n² den n değerine düşürmek gibi bir hata yapmayın).
- İkinci olarak aşağıdaki fonksiyonların büyüme tablosu size yardımcı olacaktır. Buradaki değerlere göre sadeleştirme yapacağız.
Amacımız en yavaş büyüyen logaritmik fonksiyonlara göre algoritmalarımız geliştirmek, optimizasyonları buna göre yapmaktır. (En iyi sonuç olarak). Ancak bu her zaman mümkün değildir, genellikle büyük yapılarda karesel, kübik operasyon içermesi kaçınılmazdır.
Ancak bir başka durumda ise, örneğin çok küçük boyutlu problemlerin çözümü için üssel (2ⁿ) sayıda operasyon içeren algoritmalar oldukça pratiktir. Küçük yapılarda bu karmaşıklık bize problem yaratmayacaktır.
Gelelim zor ve karmaşık örneklere. Ve işin derinlemesine…Önce asimtotik karmaşıklık anlatılacak, devamında örneklere geçilecektir.
Asimtotik Karmaşıklık
Yukarıda bahsettiğimiz çalışma zamanını bulurken bunu kategorilere ayırıyoruz gibi düşünebiliriz birazdan yapacaklarımızı. En iyi , ortalama ve en kötü karmaşıklık olarak sınıflandırabiliriz. Fonksiyonel olarak açıklamaktan ziyade anlaşılır olması için basitleştirdim. Tanıma gelecek olursak,
fonksiyonlar içerisindeki önemsiz kısımlar ve katsayılar atılarak basitleştirilir ve gerçek fonksiyona yaklaşık bir değer bulunur. Girişin büyümesine bağlı olarak fonksiyonun büyümesinde en büyük etkiye sahip olan parametre alınır.
Big O : Algoritmanın cevap verebileceği en yavaş süre,üst sınırını belirler.(worst)
Big Theta : Herhangi bir giriş için verdiği tepki(average)
Big Omega : Algoritmanın cevap verebileceği en hızlı süre, alt sınır(best)
Buradaki seçim bize kalmış. Hangi aralıkta algoritmamızı değerlendirmek istiyorsak ona göre karmaşıklığı baz alabiliriz. Kullanım ihtiyacına göre bu şekillenecektir. Ancak genel bir tanı itibariyle en kötüyü bilirsek, ortalama ve en iyi durumu da tahmin etmek için fikrimiz olabilir. Genellikle Big O notasyonu hesaplanıp algoritma karmaşıklığı bulunur .
Genellikle döngülerde (yani tekrarlı iterasyonlarda) bunların döndüğü son sayıya kadar olan kısım karmaşıklığı verir.
- 1.döngüde i<N ifadesi bize maximum N kere bu döngünün döneceğini söyler.
- 2.döngüde gene aynı ifade var. j<N, ancak üstteki döngü ile iç içe olduğu için maksimum N*N(N²)kere bu döngünün icra edeceği söylenebilir.
- 3.Döngü için 1 ve 2. iterasyonların karmaşıklığı(N*N) * N kere icra edileceği söylenebilir.(N³)
- En alt kısımdaki count(cnt) ifadesi, girişlere bağlıdır. Bunun için maksimum N³ kere icra edileceği söylenemez. Çünkü toplamlarının 0 olacağı durumlar göz önünde bulundurulmalıdır. Bunun için x(girişe bağlı) olarak ifade edilmektedir.
Bu örnekteki tilde yaklaşımı ile Big O ~N³ olarak bulunur.
Her for döngüsünde, otomatik olarak N kere döner, veya N² olarak direk yazıp geçilmemesi gerekmektedir. Çünkü düşük bir ihtimal de olsa koşul ve iterasyon eşitliğine bağlı olarak bu karmaşıklık değişebilir. Örneğin aşağıdaki kod parçası, linaritmiktir → O(nlogn)
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j = 2*j)
op();Merak edenler için: (N² /2) ve (N³ / 6) ifadelerinde neden 2 ye ve 6 ya böldük ? sorusunun cevabı için, bulabildiğim bilgi ve kaynaklar neticesinde Toplam Sembolünün özelliği olmasından geldiği kanısına vardım.
Bunun çözümünü yapıp kafa karıştırmak yerine, merak edenler için aşağıya toplam sembolünün 5 adet özelliğini ekledim. Bunların bilinmesi, karmaşıklık analizinde çözüm yaparken anlamamız için büyük fayda sağlacaktır.
Özyinelemesiz Algoritma Analizi
Özyinelemesiz kod örneği olarak aşağıdaki kod satırını, toplam sembolü ile matematiksel olarak çözebiliriz. Bunu yaparken yapılan karmaşıklık analizinin nasıl gerçekleştiğini derinlemesine olarak daha iyi anlayacaksınız. Ancak bu çözümü anlamanız için Toplam Sembolü Özellikleri kısmına bakıp, paylaştığım 5 özellikten yararlanmanız gerekmekte.
Tekrar belirtmekte fayda var. Bir döngüyü, kağıt üstünde toplam sembolü ile açıklayabiliyorsak bu işi anlamamızda büyük yol kat edeceğimiz kesin.
for i ← 0 to n-2 do
for j ← i+1 to n-1 do
if A[i] = A[j] return false
return true
Özyinelemeli Algoritma Analizi soru çözümü için Master Teoremi(Ana Teorem) anlatılacak ve bu konuya o makalemde devam edeceğim.
Kitap Önerisi olarak kaynakta belirttiğim kitap, bu dersin anlaşılabilmesi, kod olarak pratikler yapmanız için büyük yarar sağlayacaktır. Kitabı alamıyorsanız bile, kendi internet sitesindeki ücretsiz olarak sunmuş olduğu özet bilgilerden yararlanabilirsiniz.
Ek Kaynaklar:
