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.

[java]

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);//         1         A

System.out.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.out.print(i +" "); //               n         E

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

{

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

}

}

}

}

[/java]

Ö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+ 2n²çıkmaktadır.

Fakat n² 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 n² diyebiliriz.

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