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.
Veri Yapıları — Ünite 5 Soru-Cevap
Veri Yapıları (BIL207U) soru-cevapları.
Arama algoritmalarının çalışma prensibi nedir?
Web arama problemleri neye odaklanır?
p>Web arama problemleri, genellikle insan sorgularıyla oldukça alakalı belgeleri filtrelemeye ve bulmaya odaklanmaktadır.
Klasik arama algoritmaları nasıl değerlendirilir?
Klasik arama algoritmaları, bir çözümü ne kadar hızlı bulabileceklerine ve bulunan çözümün optimal olup
olmadığına göre değerlendirilir.
Arama algoritmaları nasıl daha hızlı veya daha verimli hâle getirilebilir?
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.
Doğrusal arama nedir?
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.
Ardışık arama nasıl çalışır?
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.
Aranılan elemanın mevcut olmadığı hangi durumda ortaya çıkar?
Koleksiyondaki elemanlar biterse aranılan elemanın mevcut olmadığı sonucu ortaya çıkmaktadır.
Kod çıktısı nasıl elde edilir?
Zaman karmaşıklığı: O(N)
Algoritmanın kullandığı alan (Space Complexity): O(1)
olarak elde edilmektedir.
Doğrusal aramayı özyinelemeli olarak çözmek için izlenecek yollar nelerdir?
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.
En iyi durum ne zaman ortaya çıkar?
En iyi durum, aranan eleman listenin/dizinin başında bulunduğunda ortaya çıkmaktadır.
Bir karşılaştırma yapıldığında zaman karmaşıklığı nasıl ifade edilir?
Yalnızca bir karşılaştırma yapıldığından zaman karmaşıklığı O(1)’dir.
Doğrusal aramanın ortalama durum karmaşıklığı nasıl ifade edilir?
Doğrusal aramanın ortalama durum karmaşıklığı da O(n)’dir.
En kötü durum ne zaman oluşur?
En kötü durum, hedef öge listenin sonunda bulunduğunda veya liste/dizide bulunmadığında ortaya çıkar.
Algoritma için herhangi bir yardımcı alana ihtiyacımız olmadığından doğrusal aramanın uzay karmaşıklığı nedir?
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 nedir?
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.
Aralıklı aramada dizi her aşamada kaç aralığa bölünür?
Burada dizi her aşamada 2 veya 3 aralığa bölünmüştür.
Dizi aralıklara bölündükten sonra alt aralığın uzunluğu 0 olana kadar kaç alt aralığa bölünü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.
Aralıklı aramada en iyi durum (Best Case) 0(1) nedir?
Eleman orta dizinde bulunma durumudur, yalnızca bir karşılaştırma gereklidir.
Aralıklı aramada ortalama durum (Avarage Case) nedir?
Ögeyi bulmak için her indisde yapılan aramaların zaman karmaşıklıklarının ortalamasıdır.
Aralıklı aramada en kötü durum (Worst Case) nedir?
Tekrarlama ilişkisi nedeniyle O(logn (taban 2)).
Aralıklı aramada uzay karmaşıklığının değeri nedir?
Girdi olarak verilen dizi uzunluğu dışında herhangi bir boşluk kullanılmadığı veya oluşturulmadığı için O(1)’dir.
Üçlü arama tekniği nasıl uygulanı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 fark nedir?
İ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.
İkili aramanın avantajları nelerdir?
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.