Algoritmanın Analizi

Algoritmanın analizi zaman(hız) ve hafıza(kapladığı yer) ile ilgilidir. Yani yazdığımız program ne kadar çok yer kaplıyor ve yavaş çalışıyorsa, o kadar kötü demektir. Tersi durum ise algoritmanın ne kadar iyi olduğunu gösterir. Örneğin, 100 tane rastgele numarayı küçükten büyüğe doğru sıralamamız istensin. Bu durumda kullanacağımız algoritma aslında çok önemlidir. Belki biz algoritmanın hızını fark etmeyiz ama (şu anki donanımlar yüksek işlem yapabildiğinden) sayı büyüdükçe örneğin 1 000 000 olduğunda belki de bizi rahatsız edecektir. Bu noktada yazacağımız algoritmayı iyi analiz etmeliyiz. İç içe bir sürü for döngüsü yazmak yerine tek for ile halletmeye çalışsak işlemciyi ve hafızayı daha az yorarız.

Yazılan bir algoritmayı analiz ederken, her bir satır kodun ne kadar süre çalıştığını, kaç kere tekrarlandığını iyi analiz etmeliyiz.

Bazen yazdığımız algoritmanın çalışma süresi her defasında değişebilir. Örneğin random sayılar üreten bir sistemde sıralama yapmak istiyorsak bunun sıralı gelme durumu en iyi durum analizini ifade eder. Eğer ters bir şekilde sıralı halde gelirse, bu da en kötü durum analizini ifade eder. Rastgele bir veriyle yapılan analiz de ortalama durum analizidir.

public static void main(String[] args) {

Scanner <span style="text-decoration: underline;">scan</span> = new Scanner(System.<i>in</i>);//         1         A

System.<i>out</i>.println("Lütfen bir sayı giriniz");// 1         B

int n = scan.nextInt() ; //                      1         C

for (int i = 0; i < n; i++)  //                  n+1       D

{

System.<i>out</i>.print(i +" "); //               n         E

for (int j = 0; j < n; j++) //             n*(n+1)   F

{

System.<i>out</i>.print(j +" "); //         n*n       G

}

}

}

}

Örneğin yukarıdaki algoritmayı analiz edersek, A,B,C satırındaki komut 1 kere çalışacaktır.

D Satırındaki komut ise i=0 dan n e kadar yani, n imiz örneğin 5 olursa, 0,1,2,3,4 değerleri için çalışacaktır. Bir de 5 değeri için çalışarak, kendisine uygun gelmediği için for dan çıkacaktır. Yani toplamda 6 kere çalışmış olacaktır. Bu yüzden n+1 tekrarda sonlanacaktır.

E satırı ise, n kadar çalışacaktır.

F satırı, aynı D satırı gibi n+1 kere çalışacaktır. Fakat D satırındaki for döngüsü içinde yer aldığından, D satırının çalışma sayısının çarpımıyla tekrar sayısı bulunmalıdır. Dolayısıyla n*(n+1) kere çalışır.

G satırı ise E satırındaki gibi n kere çalışması gerekmektedir. İç içe for olduğundan bir D satırındaki for, çalışma sayısını etkileyecektir. Bu yüzden n*n şeklinde olmalıdır.

Toplam maliyet= 1 + 1 + 1 + (n+1) + n + (n * (n+1)) + n*n = 4+3n+ 2n2çıkmaktadır.

Fakat n2 varken, 4 ve 3n ifadeleri anlam ifade etmemektedir. Yani en yüksek dereceli terimi alırsak kabaca algoritmayı analiz etmiş oluruz.

Bu yüzden bu algoritmanın karmaşıklığına n2 diyebiliriz.

Gösterimi ise şöyle yapılmaktadır. M = O(n2)

Hakkında Ali Demirci

Ben Ali Demirci... 1991 Ankara doğumluyum. Ankara da yaşıyorum. Fırsat buldukça öğrendiklerimi burada paylaşıyorum. Java ile haşır neşirim. Android'den asla vazgeçemem. Öğrenmeye bayılırım. Yeni şeyler öğrendiğimde, geçmişteki projelerimde keşke böyle yapsaydım diye çok üzülmüşümdür. O yüzden öğrenmekten korkmayın. Takıldığınız yerleri mutlaka sorun. Biliyorsam yanıt veririm. Bilmiyorsam yol gösteririm. Teşekkürler :)

Kontrol Et

Regex Nedir? Nasıl Kullanılır?

Regex(Regular Expression) yani düzenli ifadeler, metinlerde aranan bir tümceyi kolayca bulmamızı sağlayan bir çeşit algoritmadır. Yani …

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir