BİL207U-VERİ YAPILARI
Ünite 5: Arama Algoritmaları
Giriş
Bilgisayar bilimlerinde önemli konulardan birinin arama algoritmaları olduğu söylenebilir. Bu algoritmalar, bir veri yapısında belirli bir verinin aranması için geliştirilmiştir. Arama yapılan veri yapısı; array, liste veya graf olabilir. Arama algoritmaları; belirli bir veri yapısı içinde saklanan veya bir problem alanının arama alanında hesaplanan bilgileri, kesintili veya sürekli değerlerle almak için çalışır. Uygun arama algoritması genellikle aranmakta olan veri yapısına bağlıdır ve ayrıca verilerle ilgili ön bilgileri de içerebilir. Arama ağaçları (search trees), karma haritalar (hashmaps) ve veri tabanı dizinleri (database indexes) gibi özel olarak oluşturulmuş veri tabanı yapıları ile arama algoritmaları daha hızlı veya daha verimli hâle getirilebilir.
Sıralı/Ardışık Arama (Sequential/Linear Search)
Veri elemanları, liste gibi bir koleksiyonda depolandığında bunların doğrusal veya sıralı bir ilişkisi olduğu söylenebilir. Her veri elemanı, diğerleriyle ilişkili bir konumda saklanır. Listelerde bu göreli konumlar, tek tek elemanların dizin değerleridir. Bu indeks değerleri sıralı olduğu için sırayla aralarında gezmek mümkündür. Bu süreç, bahsedeceğimiz ilk arama tekniği olan sıralı aramayı doğurmaktadır. Doğrusal arama; listenin bir ucundaki elemandan başlayan ve listenin her bir elemanını istenen eleman bulunana kadar geçen, bulunamadığı durumda aramaya veri kümesinin sonuna kadar devam eden sıralı bir arama algoritması olarak tanımlanmaktadır. En kolay arama algoritmasıdır. Aşağıdaki şema ardışık aramanın nasıl çalıştığını göstermektedir. Listedeki ilk ögeden başlayarak aranılan eleman bulunana veya listenin elemanları tükenene kadar temeldeki sıralı diziyi izleyerek elemanlar arasında geçiş yapılmaktadır. Koleksiyondaki elemanlar biterse aranılan elemanın mevcut olmadığı sonucu ortaya çıkmaktadır.
Doğrusal Arama Özyinelemeli (Recursive) Yaklaşım
Doğrusal aramayı özyinelemeli olarak çözmek için aşağıdaki adımlar takip edilebilir:
• Dizinin boyutu sıfırsa ögenin bulunmadığını gösteren -1 döndürülmelidir. Bu aynı zamanda bir özyineleme çağrısının temel koşulu olarak da ele alınabilir. • Diğer durumda, dizideki geçerli dizindeki ögenin anahtara eşit olup olmadığı kontrol edilmelidir yani arr[boyut – 1] == aranan_kelime • Eşit ise bulunan anahtarın dizinini döndürün.
Zaman Karmaşıklığı
En İyi Durum (Best Case) - O(1)
En iyi durum, aranan eleman listenin/dizinin başında bulunduğunda ortaya çıkmaktadır. Yalnızca bir karşılaştırma yapıldığından zaman karmaşıklığı O(1)’dir.
Ortalama Durum (Average Case) – O(n)
Doğrusal aramanın ortalama durum karmaşıklığı da O(n)’dir.
En Kötü Durum (Worst Case) – O(n)
Burada n, listenin/dizinin boyutudur. En kötü durum, hedef öge listenin sonunda bulunduğunda veya liste/dizide bulunmadığında ortaya çıkar. Tüm listedeki elemanların üzerinden geçilmesi gerekmektedir ve bu işlem için n tane karşılaştırma yapılması gerektiğinden zaman karmaşıklığı O(n)’dir.
Uzay Karmaşıklığı
Algoritma için herhangi bir yardımcı alana ihtiyacımız olmadığından doğrusal aramanın uzay karmaşıklığı O(1)’dir.
Aralıklı Arama (Interval Search)
Burada dizi her aşamada 2 veya 3 aralığa bölünmüştür. Dizi aralıklara bölündükten sonra bulunacak elemanın beklendiği aralığı belirlenmektedir ve bu aralık daha sonra 2 veya 3 alt aralığa bölünerek alt aralığın uzunluğu 0 olana kadar aynı işlem tekrar edilmektedir. Elemanların artan veya azalan sırasına göre aranan eleman için veri setinin sadece belirli kısımlarının kontrol edildiği algoritmaya aralıklı arama denir.
Binary Search
İkili arama, sıralanmış elemanlar üzerinde verimli bir şekilde çalışan bir tür aralıklı arama algoritmasıdır. Aranan elemanın listenin orta ögesiyle karşılaştırıldığı bir böl ve yönet algoritmasıdır. Eşitlerse hedefin orta konumda bulunduğu anlamına gelir. Aksi takdirde arama alanı yarıya indirilir yani hedef < orta öge veya hedef > orta öge olmasına bağlı olarak listenin sol ve sağ yarısından herhangi birine ikili arama uygulanır. Bir eşleşme bulunana veya dizinin boyutu 1’e ulaşana kadar bu işleme devam edilir.
Zaman Karmaşıklığı
En İyi Durum (Best Case) O(1)
Eleman orta dizinde bulunma durumudur, yalnızca bir karşılaştırma gereklidir.
Ortalama Durum (Average Case)
Ögeyi bulmak için her indisde yapılan aramaların zaman karmaşıklıklarının ortalamasıdır bu nedenle dizi, her yinelemede yarıya bölündüğünden şu şekilde hesaplanmaktadır:
n -> n/2 -> n/4 -> n/8….. n/(2^k)
Yani bir tekrarlama formülünü takip eder: T(n) = T(n/2) + c (c sabit)
Bu ilişki, bir Tekrarlama Ağacı (Recurrence Tree) veya Ana Yöntem kullanılarak çözülebilir dolayısıyla O(log n (taban 2)) karmaşıklığını verir.
En Kötü Durum (Worst Case)
Tekrarlama ilişkisi nedeniyle O(logn (taban 2)).
Uzay Karmaşıklığı
Girdi olarak verilen dizi uzunluğu dışında herhangi bir boşluk kullanılmadığı veya oluşturulmadığı için O(1)’dir.
Üçlü Arama (Ternary Search)
İkili arama gibi üçlü arama da sıralanmış diziler üzerinde çalışan bir tür aralıklı arama algoritmasıdır. Üçlü arama, sıralanmış bir dizideki herhangi bir ögenin konumunu bulmak için kullanılan bir arama tekniğidir. Dizi, yalnızca bir orta ögenin kullanıldığı ikili arama için iki bölüme ayrılırken üçlü arama, dizinin üç bölüme ayrılmasını gerektirir ve iki orta ögeye sahiptir ancak bu teknik kullanılarak aranacak dizinin sıralı bir dizi olması gerekmektedir.
İkili ve üçlü arama arasındaki tek fark, üçlü aramada orta1 ve orta2 olmak üzere iki orta nokta kullanarak dizi[sol, sağ] şeklinde üç parçaya bölünmesidir; burada orta1 = sol + (sağ - sol) / 3 ve orta2 = sağ - (sağ - sol) / 3. Her yinelemede arama uzayının 2/3’ü yok sayılır ve hedef elemanın bulunabileceği aralık seçilir.
Algoritma
• Aranan eleman, ilk orta öge olan orta1 ile karşılaştırılır. Eşitse orta1 döndürülür; eşit değilse aranan eleman daha sonra orta2 ile karşılaştırılır ve eşitse aynısı döndürülür. • orta1 veya orta2’ye eşit değilse aranan elemanın orta1’den küçük olup olmadığı kontrol edilir. Eğer küçükse o zaman ilk bölüme geri dönülür. • Değilse anahtarın orta2’den büyük olup olmadığı kontrol edilir. Eğer evet ise dizinin üçüncü kısmına geri dönülür. • Değilse dizinin orta kısmına geri dönülür.
Zaman Karmaşıklığı
En İyi Durum (Best Case)
Aranan elemanın orta dizinde mevcut olduğu durumdur, yalnızca bir karşılaştırma gereklidir. O(1) karmaşıklığındadır.
Ortalama Durum (Average Case)
Ögeyi her indekste bulmak için zaman karmaşıklıklarının ortalamasıdır bu nedenle dizi her yinelemede yarıya bölündüğünden şu şekildedir:
n -> n/2 -> n/4 -> n/8….. n/(2^k)
Yani formülize edilebilen bir tekrarlama ilişkisi izler: T(n) = T(n/2) + c (c sabittir)
Bu ilişki, bir Tekrarlama Ağacı veya Ana Yöntem kullanılarak çözülebilir, dolayısıyla O(log n (taban 2)) karmaşıklığını verir.
En Kötü Durum (Worst Case)
Tekrarlama ilişkisi nedeniyle O(log n (taban 2)).
Uzay Karmaşıklığı
Girdi olarak verilen dizi uzunluğu dışında herhangi bir alan kullanılmadığı veya oluşturulmadığı için O(1) olarak hesaplanır.
İkili Aramanın Avantajları
• Hem kavramları hem de uygulamayı anlamak son derece basittir. • Sıralanmış bir dizi gerektirse de, her yinelemede tüm koleksiyonu ikiye böldüğü için uzun listelerdeki bir ögeyi oldukça verimli bir şekilde aramaktadır. • Hedef eleman dizinin orta elemanı ile eşleştiğinde, arama işi O(1) zaman karmaşıklığında gerçekleşir.
Hangi Algoritma En İyisidir?
Bu sorunun cevabı aslında kullanılacak duruma göre belirlenmektedir. Sıralanmış bir dizi verildiğinde Aralıklı Arama, arama işini daha kısa sürede gerçekleştirecektir. Sıralanmamış bir dizi verildiğinde diziyi sıralamak O(nlogn) zaman karmaşıklığında gerçekleşecektir. Bu zaman karmaşıklığı ile birlikte Aralıklı Aramayı kullanmak yerine Sıralı Arama ile arama işi, O(n) zaman karmaşıklığında gerçekleşecektir.