Algoritma Karmaşıklığı Nedir ? Zaman ve Hafıza Karmaşıklığı Nedir ? Nasıl Hesaplanır ?
Algoritmanın
Zaman ve Hafıza Karmaşıklığı
Bilgisayar
bilimleri ve benzeri bilimlerde istenilen soruya karşılık her
zaman istenilen cevaplar en hızlı veya en kesin sonucu verecek
yöntemler olmayabilir. Her zaman bulunduğumuz durumları göz
önünde bulundurarak sonuçlar üretmeyiz. Bir proje için bazen
zaman daha önemli olacakken bazen de kesinlik ve bu yönden
de harcanacak bellek miktarı daha önem arz etmiş olabilir.
Bu
durumlar altında kullandığımız algoritmaların bize olan zaman
ve hafıza maliyetlerini hesaplamak, bunlar hakkında bilgi sahibi
olmak çok önemlidir. Bu iki terim aslında beraber algoritmanın
verimliliğini belirtiyor. İyi bir algoritmadan az yer kaplaması ve
az zaman harcaması beklenir. Burada çoğu zaman bir takas söz
konusu ve bu biraz ters orantılı olabiliyor.
Hafıza
Karmaşıklığı
Hafıza
karmaşıklığı algoritmanın işlevini yerine getirmesi için
kullandığı bellek miktarı olarak söylenebilir. Bunun için
öncelikle genel olarak bilinen programlama dilleri için veri
yapıları ve onların boyutlarını verelim. Bunların belli
programlama dillerine göre değiştiğini unutmayın. Ben çokça
kullanılmış olanları vereceğim siz isterseniz ayrıca çoğu
kaynakta bulabilirsiniz.
Öncelikle
basit bir örnek verelim
{ int x = 1,y = 2, z = 3; int toplam = x + y + z; return toplam; }
Yukarıdaki
tabloya göre öncelikle değişkenlere bakarsak 4 tane int değişkeni
olduğunda bunları basitçe 4 * 4 olarak hesaplayıp 16 değerine
ulaşabiliriz. Burada return değerini ekleyerek bu kod parçasının
karmaşıklığının 16 + 4 = 20 olacağını söyleyebiliriz.
int toplam(int dizi[], int n) { int x = 0 for (int i = 0; i < n; i++) { x = x + dizi[i]; } return x; }
Değişkenlere
bakarsak
- n (dizinin uzunluğu) , x , i ve return x değerleri için 4'er byte yer ayrılmaktadır.
- dizi[] dizisi int türünden ve n kadar yer kapladığından bize masrafı 4 * n kadardır.
Toplamda
bize maliyeti 4*n + 16 kadar olur.
Bu
algoritmanın karmaşıklığı n kadar artacağı için düzenli bir
artış olacağından lineer yer karmaşıklığına örnektir.
Algoritmalar çoğu zaman böyle lineerlik göstermez.
Algoritmalarımızı yazarken her zaman hafızayı fazla yormama
üzerinde düşünmeli gereksiz değişkenlerden, tekrarlardan
kaçınmalı ve ihtiyacımız doğrultusunda kullanmaya özen
göstermeliyiz.
Zaman Karmaşıklığı
Zaman
karmaşıklığı algoritmanın tamamlanma süresine karşılık
gelmektedir. Burada algoritmanın gerçekleştireceği işlemler
büyük önem taşır. Belli algoritmalar için bu işlemleri toplam
bir sayı olarak belirtebiliriz ve genel terminolojiye göre de N
diyelim. Örnek vermek gerekirse eğer elimizde bir sıralama
problemi var ise ve sıralayacağımız bir dizi ise sıralanacak
eleman sayısı N sayımıza eş değerdir ki bu dizinin boyutudur.
Elimizdeki problemi bir graf problemi olarak düşünürsek de toplam
düğüm ve doğruları N ile ifade etmemiz gerekir.
Bir
algoritmanın çalışma süresi çok fazla etkene bağlıdır.
Kullandığı bilgisayarın özelliklerinden kullandığı işletim
sistemine arkada çalışan programlara gibi sayılabilecek bir çok
faktör buna etki edebilir. Karmaşıklığı hesaplarken bu
faktörler göz önüne alınmadan sadece kod üzerinde analiz
yapılarak sonuca ulaşılır. Burada asimptotik notasyon (Asymptotic
notation) adı verilen bir standart notasyon
uygulamaktayız. Bu standart ile bu bağımlılıklardan kurtularak
kod üzerinde bir analiz yapabilmekteyiz. Öncelikle bu notasyondaki
birkaç terimden bahsetmeliyiz.
-Big
O Notasyonu – en kötü durum
-Big Omega Notasyonu ( Ω ) - en
iyi durum
-Big
Teta Notasyonu (Θ) – ortalama durum
Basitçe
önceden hepsini açıklamak gerekirse Big O notasyonu bizim için
olabilecek en kötü durumu gösterirken Big Ω (Omega) Notasyonu
bizim için en iyi durumu ifade eder. En basitinden örnek vermek
gerekirse bir sayı dizisinde N kadar eleman olduğunu varsayalım.
Problemimiz de bu diziden bir sayıyı bulmaksa aradığımız sayı
dizinin ilk elemanı olabileceği gibi son elemanı da olabilir.
Sayıyı ararken her yaptığımız işlemi bir birim olarak ifade
edersek Big Ω için bu durum bir birim kabul edilebilir ve Big Ω
(1) olarak gösterilir. Big O için de N kadar olabileceği söylemiş
ve dizinin sonuna kadar gitmemiz gerekebileceğini söylemiştik ve
bu durumda da Big O (N) kadar bir değeri olacağını
söyleyebiliriz. Big Teta notasyonu ise bu iki durumun ortalamasını
ifade eder. Algoritmalar tasarlanırken her zaman en önem taşıyanı
Big O notasyonu olmuştur. Her zaman en kötü duruma odaklanmalı
onun üzerinden geliştirmeler yapmalıyız.
Notasyonlar
için hesaplanacak değerler için katsayılar ve sabit değerler bir
önem taşımaz. Sayıları sonsuza götüreceğimiz değerlerin en
büyük dereceli ifadenin karakteristiği tüm ifadeyi etki
edeceğinden bizi ilgilendiren en büyük dereceli terimdir.
- O(2N) = O(N)
- O(N + 5) = O(N)
- O(N² + N + 5) = O(N²)
- O(19052019) = O(1)
- O(5logN) = O(logN)
Bu
bilgiler doğrultusunda birkaç örnek inceleyelim.
İlk
örneğin 1 den başlayarak N'e kadar toplama yapan bir algoritma
olduğunu varsayalım. Yani N = 3 ise 1 + 2 + 3 = 6 fonksiyonun
çıktısı olmalıdır. Bu problemin üzerine algoritmalar
gerçekleştirip zaman karmaşıklıklarını ölçelim.
İlk
çözümümüzde genel olarak herkesin aklından geçen ilk çözümü
gösterirsek
int Topla (int N) { int toplam = 0; for (int i = 1; i <= N; ++i) { toplam = toplam + i; } return toplam; }
Şeklinde
bir algoritma işimizi görecektir. Burda N kadar bir işlem
yapılacağından problemin bize maliyeti O(N) olarak
belirleyebiliriz.Burada elbetteki tek zaman maliyeti döngünün
içindeki yapı değildir. Her ne kadar diğer satırların da bize
bir maliyeti olsa da önceden de bahsedildiği üzere en önemli
etken üzerinde durup ana maliyet olarak onu ifade ederiz. Burada da
for döngüsü bizim için ana etkendir.
Çoğumuz
tarafından bilinen çok daha az masraflı olmasına rağmen her
zaman ilk akla gelmeyen bir çözümü daha sunalım
int Topla (int N) { return ( N * ( N + 1) / 2); }
Bu
çözümde Big O değerimiz O(1) olucaktır. Çünkü tek adımda
problemi çözmüş olduk.
Not
: Big O notasyonunda eğer işlemin sabit (constant) bir zaman
harcayacağı belliyse satır sayısı göz önüne alınmadan Big O
değeri O(1) dir.
Daha
bir zahmetli bir çözüm
int Topla (int N) { int toplam = 0; for ( int i = 1; i <= N; ++i) { for(int j = 1; j <= i; ++j) { toplam = toplam + 1; } } return toplam; }
Şüphesiz
ki bu fonksiyon ile de aynı çözüme ulaşabiliriz. Fonksiyona
biraz daha yakından bakarsak
ilk
for döngüsü 1 kere çalıştığında ikinci döngüde 1 kere
çalışacaktır. Aynı şekilde 2 3 diye devam edecek olan bu döngü
N kere tekrar edicektir. Bunları toplarsak
1
+ 2 + 3 + .... + = N * (N + 1) / 2
ifadesini
elde etmiş oluruz ve bizi çözümümüze ulaştırmış olur.
Karmaşıklığımız da
O(
( N² – N ) / 2 ) = O(N²)
olur.
Görüldüğü
üzere bir problem için üç farklı zaman karmaşıklığına sahip
algoritmalar üretmek mümkün. Zaman karmaşıklığı ölçülürken
N' e bağlı olan döngülerden bahsedildiğini unutmamak gerekir.
Aynı
söylediklerimizi Selection Sort algoritması için de uygulamak
istersek
void selection(int dizi [ ], int N) { int temp, i, j, en_kucuk; for(i = 0;i < N-1; i++) { en_kucuk = dizi[i]; for(j = i + 1;j < N; j++) { if(dizi[j] < en_kucuk) en_kucuk = dizi[j]; } temp = dizi[i]; dizi[i] = en_kucuk; en_kucuk = temp; } }
Bu
algoritmanın karmaşıklığı da O(N²) olarak ölçülebilir.
En bilinen sıralama algoritmaları için Big Notasyonu değerleri yukarıda belirtilmiştir.
O(2^N)
ifadesi
Algoritmanın 2'nin üzerine katlanarak gittiği durumları ifade eder. Bu yapı için
en temel örnek fibonacci dizisi verilebilir.
int Fibonacci(int N)
{
if (N <= 1) return N;
return Fibonacci(N - 2) + Fibonacci(N - 1);
}
O(logN)
ifadesi
Logaritma
matematik derslerinde gördüğümüz üzere üstel ifadenin tam
olarak tersidir.Yani 2³ = 8 olduğunu aynı şekilde logaritmasının
da log2(8) = 3 olarak yazılabildiğini üstel ifadenin sıralı
çarpımları ifade ederken de logaritmanın bölmeleri ifade
ettiğini biliyoruz. Bu açıklamadan sonra bir döngüde bize
verilen N aralığı her seferinde belli bir oranda azalmaya
gidiyorsa logaritmik olarak bir davranış göstereceğini bizim için
O(logN) anlamına geleceğini söyleyebiliriz. Örnekle açıklamak
gerekirse Binary Search bunun için eşsiz olacaktır. Algoritma bu
linkten detaylıca incelenebilir. Binary Search'un kısaca
mantığından bahsedecek olursak da yine N elemanlı
bir sıralı dizimiz olduğunu varsayarak devam
edelim. Binary Search işe medyanı seçerek başlar ve aradığı
elemanın medyandan küçük veya büyük olduğunu teyit eder.
Dizi
= { 5, 12, 16, 23, 34, 42} şeklinde bir dizi verilmiş ve bizim
aradığımız sayı 42 ise medyandan büyük olduğu kolayca
anlaşılır. İfade edilmesi gereken nokta elimizde hiçbir bilgi
yokken aralığımızın N boyutunda olduğu görülür. Fakat
elimize sayının medyandan büyük olduğu bilgisi gelince
aradığımız sayının medyanın sağında kalan kısım olduğunu
anlarız ve aralığımız N/2 kadar azalır. Tekrar medyan seçilir
ve aynı işlem tekrar eder. Bu azalma işlemi logaritmik olarak
devam ettiği için Big O (logN) olarak ifade edilir.
Yorumlar
Yorum Gönder