- Hedef
- Geçerli blok
- Karşılaştırılan
- Elenen
- Bulunan
Atlamalı arama
Atlamalı arama, doğrusal arama ile ikili arama arasında yer alır. Sıralı bir listede m sıralık atlamalarla ilerler ve her bloğun yalnızca son değerine bakar; bunu, son değeri hedeften küçük olmayan bir bloğa ulaşana kadar sürdürür. Sonra o bloğu başından tarar. Değeri ve atlama boyunu seçin, atlamaların ve taramanın kaç karşılaştırma aldığını izleyin. Aramayı izlemek için Oynat'a, her seferinde bir karşılaştırma ilerlemek için Adım ve Geri'ye basın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin. Kesikli çizgi aradığınız değeri, gölgeli kısım ise geçerli bloğu gösterir. Atlamalı arama sıralı bir liste gerektirir, bu yüzden sırasız bir liste önce sıralanır. Değeri, atlama boyunu, çubuk sayısını seçin ya da kendi sayılarınızı yazın. Tahta seçiliyken ok tuşları adım atar, boşluk tuşu oynatır ve duraklatır, Home ve End başa ve sona atlar.
Nasıl çalışır
- Aranacak değeri, atlama boyunu ve çubuk sayısını seçin. Ya da kendi sayılarınızı yazın: atlamalı arama önce onları sıralar.
- Oynat'a basın ya da her seferinde bir karşılaştırma ilerlemek için Adım ve Geri'yi kullanın. Aramanın herhangi bir yerine atlamak için adım kaydırıcısını sürükleyin.
- 40 çubukta 2 ve 8 atlama boylarını deneyin ve karşılaştırma sayılarını √n ile kıyaslayın.
Atlamalı arama nasıl çalışır
Sıralı listeyi m değerlik bloklara bölün. İlk bloğun son değerine bakın. Hedeften küçükse hedef o blokta hiçbir yerde olamaz; bu yüzden bir sonraki bloğun sonuna atlayın ve yeniden bakın. Bir bloğun son değeri küçük olmadığı anda hedef yalnızca o blokta olabilir: bloğun başına dönün ve hedefi bulana ya da geçene kadar değerleri tek tek kontrol edin.
Atlama boyunu seçmek
n değerde atlamalar en fazla n/m, tarama en fazla m karşılaştırma alır. Küçük atlamalar taramayı kısaltır ama atlama sayısını artırır; büyük atlamalar bunun tersini yapar. n/m + m toplamı m = √n olduğunda en küçüktür ve yaklaşık 2√n karşılaştırma verir: 40 değer için en fazla 13; doğrusal aramada 40, ikili aramada 6. Atlamalı arama hiçbir zaman bir bloktan fazla geri gitmez; bu, veride geri gitmek yavaş olduğunda işe yarar.
Sık sorulan sorular
Atlamalı arama nasıl çalışır?
Sıralı bir listede m sıralık adımlarla ileri atlar ve her bloğun son değerine bakar. Bu değer artık hedeften küçük olmadığında hedef yalnızca o blokta olabilir; arama da o bloğu başından tarar.
En iyi atlama boyu nedir?
Yuvarlanmış √n. Atlamalar en fazla n/m, tarama en fazla m karşılaştırma tutar ve ikisi eşit olduğunda, yani m = √n iken toplamları en küçüktür. Bu, en kötü durumda yaklaşık 2√n karşılaştırma demektir.
Atlamalı arama ikili aramadan hızlı mı?
Hayır, ikili arama daha az karşılaştırma gerektirir: yaklaşık log₂ n; atlamalı arama ise yaklaşık 2√n. Yine de veride geri gitmek pahalıysa atlamalı arama öne geçebilir, çünkü yalnızca bir kez, bir bloğun başına geri döner.
Değerler tekrar ettiğinde hangi eşleşmeyi bulur?
İlkini. Atladığı her blok hedeften küçük bir değerle biter; bu yüzden daha önceki hiçbir blokta eşleşme olamaz ve tarama bloğun başından başlar.
Sayılarım bir yere gönderiliyor mu?
Hayır. Arama tarayıcınızda çalışır ve son ayarlarınız bu tarayıcının yerel depolamasında kalır.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Editöre Git