Üstel arama - Exponential search

Üstel arama
SınıfArama algoritması
Veri yapısıDizi
En kötü durumda verimÖ(günlük ben)
En iyi senaryo verimÖ(1)
Ortalama verimÖ(günlük ben)
En kötü durumda uzay karmaşıklığıÖ(1)

İçinde bilgisayar Bilimi, bir üstel arama (olarak da adlandırılır iki katına çıkan arama veya dörtnala arama veya Struzik araması)[1] bir algoritma, tarafından yaratıldı Jon Bentley ve Andrew Chi-Chih Yao 1976'da sıralı, sınırsız / sonsuz listeleri aramak için.[2] Bunu uygulamanın birçok yolu vardır ve en yaygın olanı arama tuşunun bulunduğu bir aralığı belirlemektir ve bir Ikili arama bu aralık içinde. Bu alır Ö (günlükben) nerede ben arama tuşu listede ise arama tuşunun listedeki konumu veya arama tuşu listede değilse arama tuşunun olması gereken konumdur.

Üstel arama, sınırlı listelerde arama yapmak için de kullanılabilir. Üstel arama, aranan öğe dizinin başlangıcına yakın olduğunda ikili arama gibi sınırlı listeler için daha geleneksel aramaları bile geride bırakabilir. Bunun nedeni, üstel aramanın çalışacak olmasıdır. Ö(günlükben) zaman, nerede ben listede aranan öğenin indeksi, ikili arama ise Ö(günlükn) zaman, nerede n listedeki elemanların sayısıdır.

Algoritma

Üstel arama, belirli bir giriş değeri için sıralı, sınırsız bir listede aramaya izin verir (arama "anahtarı"). Algoritma iki aşamadan oluşmaktadır. İlk aşama, listede olsaydı arama anahtarının bulunacağı bir aralığı belirler. İkinci aşamada bu aralıkta ikili arama yapılır. İlk aşamada, listenin artan sırada sıralandığını varsayarak, algoritma ilkini arar. üs, j, değer 2 neredej arama anahtarından daha büyüktür. Bu değer, 2j önceki kuvvet olan 2, 2 ile ikili aramanın üst sınırı olurj - 1, ikili arama için alt sınırdır.[3]

// Uzunluk dizisinin dizisindeki anahtarın konumunu döndürür.şablon <typename T>int üstel_arama(T arr[], int boyut, T anahtar){    Eğer (boyut == 0) {        dönüş BULUNAMADI;    }    int ciltli = 1;    süre (ciltli < boyut && arr[ciltli] < anahtar) {        ciltli *= 2;    }    dönüş Ikili arama(arr, anahtar, ciltli/2, min(ciltli + 1, boyut));}

Her adımda, algoritma, arama anahtarı değerini mevcut arama indeksindeki anahtar değeriyle karşılaştırır. Mevcut dizindeki eleman arama anahtarından daha küçükse, algoritma tekrar eder, onu ikiye katlayarak bir sonraki arama dizinine atlar ve 2'nin bir sonraki gücünü hesaplar.[3] Mevcut dizindeki eleman arama anahtarından daha büyükse, algoritma artık arama anahtarının, eğer listede yer alıyorsa, önceki arama endeksinin oluşturduğu aralıkta yer aldığını bilir, 2j - 1ve mevcut arama dizini, 2j. İkili arama daha sonra ya arama anahtarı listede değilse bir başarısızlık sonucu ya da arama anahtarının listedeki konumu ile gerçekleştirilir.

Verim

Algoritmanın ilk aşaması Ö(günlükben) zaman, nerede ben arama anahtarının listede olacağı dizindir. Bunun nedeni, ikili arama için üst sınırın belirlenmesinde while döngüsünün tam olarak yürütülmesidir. zamanlar. Liste sıralandığından, arama dizini ikiye katlandıktan sonra algoritma, şuna eşit veya daha büyük bir arama dizininde olacaktır. ben gibi . Bu nedenle, algoritmanın ilk aşaması Ö(günlükben) zaman.

Algoritmanın ikinci kısmı da Ö(günlükben) zaman. İkinci aşama basitçe bir ikili arama olduğundan, Ö(günlükn) nerede n aranan aralığın boyutudur. Bu aralığın boyutu 2 olurj - 2j - 1 yukarıda görüldüğü gibi nerede j = günlükben. Bu, aranan aralığın boyutunun 2 olduğu anlamına gelirgünlük ben - 2günlük ben - 1 = 2günlük ben - 1. Bu bize günlük çalışma süresi verir (2günlük ben - 1) = günlük (ben) - 1 = Ö(günlükben).

Bu, algoritmaya, iki aşamanın çalışma sürelerinin toplanmasıyla hesaplanan toplam bir çalışma süresi verir. Ö(günlükben) + Ö(günlükben) = 2 Ö(günlükben) = Ö(günlükben).

Alternatifler

Bentley ve Yao, üstel arama için birkaç varyasyon önerdi.[2] Bu varyasyonlar, algoritmanın ikinci aşamasında ikili aramanın üst sınırını belirlerken, tekli aramanın tersine ikili bir arama gerçekleştirmekten oluşur. Bu, algoritmanın ilk aşamasını ikiye bölerek algoritmayı genel olarak üç aşamalı bir algoritma haline getirir. Yeni ilk aşama bir değer belirler daha önce olduğu gibi, öyle ki arama anahtarından daha büyüktür ve arama anahtarından daha düşüktür. Önceden, 2'nin bir sonraki üssü hesaplanarak tek bir şekilde belirlendi (yani, j). Varyasyonda şu önerilmektedir: bunun yerine ikiye katlanır (ör. 2'den atlama2 2'ye4 2'nin aksine3). İlk öyle ki arama anahtarından daha büyük olması, eskisinden çok daha kaba bir üst sınır oluşturur. Bir kez bu bulunur, algoritma ikinci aşamasına geçer ve oluşan aralıkta ikili arama yapılır. ve , daha doğru üst sınır üssü verir j. Buradan, algoritmanın üçüncü aşaması, 2 aralığında ikili aramayı gerçekleştirir.j - 1 ve 2j, eskisi gibi. Bu varyasyonun performansı = Ö(günlükben).

Bentley ve Yao, bu varyasyonu herhangi bir sayıya göre geneller, k, algoritmanın ilk aşamasında gerçekleştirilen ikili aramaların kiç içe geçmiş ikili arama varyasyonu. Asimptotik çalışma zamanı, çalışan varyasyonlar için değişmez. Ö(günlükben) orijinal üstel arama algoritmasında olduğu gibi zaman.

Ayrıca, sıkı bir sürümüne sahip bir veri yapısı dinamik parmak özelliği yukarıdaki sonuç ne zaman verilebilir k-iç ​​içe ikili arama, sıralanmış bir dizide kullanılır.[4] Bunu kullanarak, bir arama sırasında yapılan karşılaştırma sayısı günlüktür (d) + günlük günlüğü (d) + ... + Ö(günlük*d), nerede d erişilen son öğe ile erişilmekte olan geçerli öğe arasındaki sıra farkıdır.

Ayrıca bakınız

Referanslar

  1. ^ Baeza-Yates, Ricardo; Salinger, Alejandro (2010), "Sıralanmış diziler için hızlı kesişim algoritmaları", Elomaa, Tapio; Mannila, Heikki; Orponen, Pekka (ed.), Algoritmalar ve Uygulamalar: 60. Doğum Günü Vesilesiyle Esko Ukkonen'e Adanmış Yazılar, Bilgisayar Bilimleri Ders Notları, 6060, Springer, s. 45–61, Bibcode:2010LNCS.6060 ... 45B, doi:10.1007/978-3-642-12476-1_3, ISBN  9783642124754.
  2. ^ a b Bentley, Jon L.; Yao, Andrew C. (1976). "Sınırsız arama için neredeyse optimal bir algoritma". Bilgi İşlem Mektupları. 5 (3): 82–87. doi:10.1016/0020-0190(76)90071-5. ISSN  0020-0190.
  3. ^ a b Jonsson, Håkan (2011-04-19). "Üstel İkili Arama". Alındı 2014-03-24.
  4. ^ Andersson, Arne; Thorup, Mikkel (2007). "Üstel arama ağaçları ile dinamik sıralı kümeler". ACM Dergisi. 54 (3): 13. arXiv:cs / 0210006. doi:10.1145/1236457.1236460. ISSN  0004-5411.