Bu açıdan, algoritma analizi, bilgisayar mühendisliğinin (bilimlerinin) en önemli matematiksel dayanağını oluşturur. Matematik bilimindeki karmaşıklık teoreminin (complexity theory) bir uygulama alanı olan algoritma analizi, matematiksel yöntemlerle, bir algoritmanın performansı hakkında bilgi verir.
Neden algoritmayı analiz ederiz?
Algoritmanın performansını ölçmek için †
Farklı algoritmalarla karşılaştırmak için †
Daha iyisi mümkün mü? Olabileceklerin en iyisi mi?
Özelliklerinin analizi †
Algoritmanın çalışma zamanı†
Hafızada kapladığı alan
Bir algoritmanın performansı iç ve dış faktörlere bağlıdır.
Karmaşıklık iç faktörlerle ve daha çok da zamanla ilgilidir.
Yürütme Zamanı T(n)
Bir yazılım kodunda, toplam kaç birim işlem yapıldığının göstergesidir.
Buradaki her bir birim işlem, her bir dil (örn C# dili) ifadesi olarak ele alınabilir.
n olarak ifade edilen birim işlemlerin toplamı T(n) yürütme zamanı fonksiyonunu verecektir.
Ancak birçok algoritma veri işlediğinden dolayı, n’i belirleyen en büyük faktör veri sayısı olacaktır.
ÖRNEK
Aşağıda bir dizinin aritmetik ortalamasını bulan ve sonucu kullanıcıya geri döndüren bulortalama() adlı fonksiyonun kodu verilmiştir. Bu fonksiyonun yürütme zamanını gösteren T(n) bağıntısını elde ediniz.
ÇALIŞMA ZAMANI ANALİZİ
Bir algoritmanın performansı iç ve dış faktörlere bağlıdır. …
Algoritma 1 T1(N)=1000N …
Algoritma 2 T2(N)=N2
N değerinin 1000’den küçük olduğu durumlarda iki algoritma arasındaki çalışma zamanı ihmal edilebilir büyüklüktedir.
BÜYÜME HIZI VE BÜYÜK O (BIG O) NOTASYONU (Karmaşıklık)
Büyüme hızı bir algoritmanın performansını yansıtan en iyi göstergedir.
Büyük-O notasyonu büyüme hızını gösterir. Bir algoritmanın performansını en iyi tanımlayan matematiksel bir formüldür ve algoritmanın iç detaylarına bakılarak elde edilir.
Büyük-O girdi verisinin büyüklüğünü gösteren bir N parametresine dayanan bir fonksiyondur.
Örneğin n değerine bağlı olarak performansı (sabit a, b, c değerleri için) an2 + bn + c olan bir algoritmanın performansı O(N2)’dir
N değeri arttıkça N2 terimi baskın olacağı için büyük-O notasyonunda sadece baskın olan terim kullanılır.
Bir algoritmanın çalışma zamanı bulunduktan sonra, ne tür bir karmaşıklığa sahip algoritma olduğunu belirlemek için;
T(n) bulunduktan sonra, tüm değişkenler tek tip değişkene dönüştürülür, sabitler ve düşük dereceli terimler atılar ve en yüksek dereceli terim, O(n) karmaşıklık foksiyonunu ifade eder.
Örn: T(n) = 3n + 4 O(n) olur.
O notasyonunda yazarken en basit şekilde yazarız.
Örneğin
3n2+2n+5 = O(n2)
Aşağıdaki gösterimlerde doğrudur fakat kullanılmaz.
3n2+2n+5 = O(3n2+2n+5)
3n2+2n+5 = O(n2+n)
3n2+2n+5 = O(3n2)
BÜYÜK O (BIG O) NASIL HESAPLANIR?
Bir program kodunun zaman karmaşıklığını hesaplamak için 5 Kural;
1 Döngüler
2 İç içe Döngüler
3 Ardışık deyimler
4 If-then-else deyimleri
5 Logaritmik karmaşıklık
1. DÖNGÜLER
Bir döngünün çalışma zamanı en çok döngü içindeki deyimlerin çalışma zamanının iterasyon sayısıyla çarpılması kadardır.
Toplam zaman = sabit c * n = cn = O(N)
2. İÇ İÇE DÖNGÜLER
İçteki analiz yapılır. Toplam zaman bütün döngülerin çalışma sayılarının çarpımına eşittir.
Toplam zaman = c * n * n * = cn2 = O(N2)
3. ARDIŞIK DEYİMLER
Her deyimin zamanı birbirini etkiler.
toplam zaman = c0 + c1n + c2n2 = O(N2)
4. IF-THEN-ELSE DEYİMLERİ
En kötü çalışma zamanı:test zamanına then veya else kısmındaki çalışma zamanının hangisi büyükse o kısım eklenir.
Toplam zaman = c0 + c1 + (c2 + c3) * n = O(N)
5. LOGARİTMİK KARMAŞIKLIK
Problemin büyüklüğünü belli oranda(genelde ½) azaltmak için sabit bir zaman harcanıyorsa bu algoritma O(log N)’dir.
Örnek algoritma (binary search):
N sayfalı bir sözlükten bir sözcük arama
Sözlüğün orta kısmına bakılır
Sözcük ortaya göre sağda mı solda mı kaldığı bulunur?
Bu işlem sağ veya solda sözcük bulunana kadar tekrarlanır.
ÖRNEK
Fonksiyonların harcadıkları zamanları O notasyonuna göre yazınız.
f1(n) = 10 n + 25 n2
f2(n) = 20 n log n + 5 n
f3(n) = 12 n log n + 0.05 n2
f4(n) = n1/2 + 3 n log n
SIK KULLANILAN BÜYÜME HIZLARI
