Algoritmaların analizini yapmak için asimptotik analiz ismi verilen bir metodoloji kullanılmaktadır. Buradaki amaç algoritmanın ulaşabileceği en kötü(worst) veya en iyi(best) durumu matematiksel olarak modellemektir.Bu duruma bir algoritmanın karmaşıklığı denilmektedir.Bir algoritmanın implementasyonu yapılmış kodun karmaşıklının bulunduğu sırada bu kodun hangi programlama diliyle yazıldığı veya bu kodun çalıştığı makinenin hızı gibi durumlar göz ardı edilmektedir.Her komutun çalıştırılma süresi 1 ms olarak kabul edilir.
Örnek olarak bir tam sayıların bulunduğu bir dizide herhangi bir tamsayı arama işleminin Java koduna bakacak olursak;
public class Search { public void Sayi_Bul(int[] dizi,int sayi){ for(int i=0;i<dizi.length;i++) if(dizi[i]==sayi){ System.out.println("sayi bulundu..."); break; } } public static void main(String[] args) { int array[]={4,1,2,5,56,41,23,567,412,98,56,32}; new Search().Sayi_Bul(array, 98); } }
Sayi_Bul metodunun kodundan görüldüğü gibi,dizinin 0. elemanından başlayarak dizinin sayılarının aranan sayıya eşit olup olmağına bakılıyor.Eğer aranan sayı dizinin 0. elemanı ise o zaman bu duruma en iyi durum(best case) denilmektedir.Yok eğer arananan sayı dizinin sonuncu elemanı ise veya bu aranan sayı dizide yok ise bu duruma en kotü durum(worst case) denilmektedir,çünkü bu durumda dizinin tüm elemanları kontrol edilmektedir.
Asimptotik analizde bir algoritmanın karmaşıklığını göstermek için Big O notasyonu kullanırlır.Yukarıdaki Sayi_Bul metodunun en iyi durumu diğer işlemler göz ardı edilirse O(1)'dir.En kötü durumu ise O(N)'dir. N burada dizinin uzunluğunu ifade etmektedir.Karmaşıklı bulunurken ise en kötü durum göz onüne alınır,yani bizim metodumuzun karmaşıklığı O(N)'dir diyebiliriz.
Sıralama Algoritmalarının Karmaşıklığı.
Bilindiği gibi sıralama algoritmaları bir dizideki,listedeki vs sayıları sıralamak için kullanılmaktadır. Veri dizisinin çok büyük olduğu durumlarda bu algoritmalardan hangisini kullanmamızın daha verimli olacağını bilmemiz gerek.
Buble Sort
Karmaşıklığı O(N^2) olan diğer sıralama algoritmalarından biridir.Diyelimki bir tam sayı dizisini küçükden büyüğe sıralıyoruz.Tahmin etmesi kolaydır ki,bu yöntemde en iyi durum büyük sayıların yerleşiminin dizinin sonuna doğru olduğu durumdur,yani dizinin sıralanmış haline daha yakınlığıdır.
Buble sortda ilk sayıdan başlanarak sonraki sayi ile karşılaştırılarak yerleri degiştirilir ve ilk döngüde dizinin en büyük elemanı bulunur ve dizinin sonuna eklenir.Bu sıralama yötemindeki karmaşıklığa etki eden bir unsur ne kadar fazla yerdeğiştirme işleminin yapıldığır.Yani bir dizi tersten sıralanmış durumuna ne kadar yakınsa kodun çalışma süresi o kadar artar.
public class BubbleSort { private void ALG_BubbleSort(int[] array){ for (int i =array.length-1; i>0; i--) { for(int j=0;j<i;j++){ if(array[j]>array[j+1]){ temp=array[j+1]; array[j+1]=array[j]; array[j]=temp; } } } } }
Yukarıdaki Bubble sort kodunun yerdeğiştirme işlemlerini worst case'de ihlal etdiyimiz durumda iç-içe for döngülerinin sayesinde algoritmanın karmaşıklığı O(N^2) olmaktadır.N burada sıralanan dizinin uzunluğudur.
Quick Sort
Quick sort algoritması adından belli olduğu gibi sonuca hızlı ulaşan bir sıralama yöntemidir. Bu algoritma sayı dizisini sürekli ikiye bölerek sonuca ulaşır.
public class QuickSort { public void ALG_QuickSort(int[] arr, int low, int high) { int middle = low + (high - low) / 2; int pivot = arr[middle]; int i = low, j = high; while (i <= j) { while (arr[i] < pivot) { i++; } while (arr[j] > pivot) { j--; } if (i <= j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } if (low < j){ ALG_QuickSort(arr, low, j); } if (high > i){ ALG_QuickSort(arr, i, high); } } }
Buradaki sürekli ikiye bölme işleminin matematiksel ifadesinin en kötü durumu nlogn'dir.Burada logaritma tabanı 2'dir.Yani algoritmanın karmaşıklığı O(nlogn) olacaktir.
Bubble sort,Selection sort,Insertion sort,Quick sort sıralama algoritmalarının karşılaştırma kodlarına buradan erişebilirsiniz.
İkili Arama Algoritması
İkili arama algoritması zaman bakımından normal arama algoritmasına göre elverişli bir algoritmadır.Bu algoritma arama yaparken bir diziyi ikiye böler.Normal arama algoritmasının karmaşıklığı O(n) iken,ikili aramada karmaşıklık O(logn)'dir. Logaritmanın tabanı 2'dir.
1 int[] data; 2 int size; 3 4 public boolean binarySearch(int key) 5 { 6 int low = 0; 7 int high = size - 1; 8 9 while(high >= low) { 10 int middle = (low + high) / 2; 11 if(data[middle] == key) { 12 return true; 13 } 14 if(data[middle] < key) { 15 low = middle + 1; 16 } 17 if(data[middle] > key) { 18 high = middle - 1; 19 } 20 } 21 return false; 22 }
Fakat arama işlemlerinde zaman farkı dizinin boyutuna göre değişebilmektedir.Örneğin büyük uzunluklu dizilerde ikili arama işleminin zaman bakımından nasıl değiştiğini burdan görebilirsiniz.Değişimin grafiksel göstergesi ise;
Veri Yapıları(Hash Tables)
Geliştirilen pek çok uyuglamalarda hızlı veri ekleme,çıkarma,arama işlemlerine ihtiyaç duyulur.Hash Tabloları bu işlemleri en hızlı şekilde yapan veri yapılarından biridir.Verilere bir eşsiz(unique) anahtar ile erişilir.Bu anahtar tipi string,integer,float vs. olabilir.Tablodaki verileri bu anahtarlara indekslemek içinse Hash fonksiyonu kullanılır,ve sonuçda bir hash code üretilir.
Hash tablolarının iki türü vardır.
- Fixed Tables(Eleman sayısı oluşturma anında belirlenen tablo)
- Dynamic Tables(Eleman sayısı değişebilen tablo)
Hash tablolarında arama yapmak O(1) gibi sabit bir zaman diliminde gerçekleşir.Fakat bir çakışma durumunda bu zaman dilimi O(n) kadar artabilmektedir.Buradaki çakışma'dan kasıt kullanılan hash fonksiyonun iki farklı anahtar için aynı indeks değerini üretmesidir. Aşağıdaki kod bir Dinamik Hash tablosu kullanımına örnekdir.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | import java.util.*; public class HashTableDemo { public static void main(String args[]) { // tablo oluştur Hashtable<String, Double> bakiye= new Hashtable<String, Double>(); Enumeration<String> kisiler; String str; double balans; bakiye.put("Zara", new Double(3434.34)); bakiye.put("Mahnaz", new Double(123.22)); bakiye.put("Ayan", new Double(1378.00)); bakiye.put("Daisy", new Double(99.22)); bakiye.put("Qadir", new Double(-19.08)); //butun bakiyeleri göster kisiler = bakiye.keys(); while(kisiler.hasMoreElements()) { str = (String) kisiler.nextElement(); System.out.println(str + ": " + bakiye.get(str)); } System.out.println(); // zaranın hesabını 1000 artır balans = ((Double)bakiye.get("Zara")).doubleValue(); bakiye.put("Zara", new Double(balans+1000)); System.out.println("Zara's new balance: " + bakiye.get("Zara")); } } |
