Daha ucuz olan nedir: diziyi sıralayıp sonra arama yapmak mı yoksa eleman araması için tarama mı kullanmak?

Bağlamdan bağımlıdır.

1. Sıralanmamış bir dizide tek seferlik arama:

   • Sıralama: Sıralama karmaşıklığı genellikle $O(n \log n)$ veya $O(n^2)$'dir (algoritmaya bağlı olarak).
   • Arama (sıralamadan sonra ikili arama): $O(\log n)$.
   • Toplam: $O(n \log n)$ veya $O(n^2)$.
   • Tarama (doğrusal arama): $O(n)$.
   • Toplam: $O(n)$.
   • Bu durumda, tarama ($O(n)$) sıralama + aramadan ($O(n \log n)$ veya daha fazla) daha ucuzdur.

2. Bir dizide çoklu arama:

   • Aynı dizide $k$ arama yapılması gerekiyorsa.
   • Bir kez sıralama: $O(n \log n)$ veya $O(n^2)$.
   • Sıralamadan sonra $k$ ikili arama yapmak: $k \times O(\log n) = O(k \log n)$.
   • Toplam: $O(n \log n + k \log n)$ veya $O(n^2 + k \log n)$.
   • $k$ doğrusal tarama yapmak: $k \times O(n) = O(kn)$.
   • Toplam: $O(kn)$.
   • Büyük $k$ ($k > \log n$) için, sıralama ve ikili arama daha ucuz hale gelir: $O(n \log n + k \log n)$ karşı $O(kn)$.

3. Özel durumlar:

   • Eğer dizi zaten kısmen sıralıysa veya özel bir yapıya sahipse, daha hızlı sıralama veya arama algoritmaları mevcuttur.
   • Hash tabloları (Set veya Hash Ruby'de) ortalama $O(1)$ zaman sağlar ve genellikle sıralama veya doğrusal aramadan daha hızlıdır.

Sonuç: Tekli arama için tarama daha ucuzdur. Aynı dizide çoklu aramalar için, sıralama ve ikili arama yeterince çok arama yapıldığında daha avantajlıdır. Arama hızının kritik olduğu ve veri yapısının değiştirilebildiği durumlarda, Set veya Hash kullanımı en optimal çözümdür.

Ruby'de doğrusal arama örneği:

# Sıralanmamış dizide eleman arama
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # İlk eşleşmeyi bulduktan sonra dur
  end
end

puts found # => 8

Ruby'de sıralama ve ikili arama örneği (standart metodlar kullanılarak):

# Sıralama
array = [5, 2, 8, 1, 9, 4]
sorted_array = array.sort # Ruby'de Timsort ile O(n \log n)

# İkili arama (Ruby'de bsearch)
target = 8
index = sorted_array.bsearch_index { |x| x >= target } # O(\log n)

if index && sorted_array[index] == target
  puts sorted_array[index] # => 8
else
  puts "Eleman bulunamadı"
end