რა იაფია: მასივის სორტირება და შემდეგ ძებნა, თუ გადავლა ელემენტის პოვნას?

Контексткә бәйле.

1. Бер тапкыр эзләү сортланмаган массивта:

   • Сортлау: Сортлау вакыты гадәттә $O(n \log n)$ яки $O(n^2)$ (алгоритмгә бәйле).
   • Эзләү (бинарлы, сортлаганнан соң): $O(\log n)$.
   • Гомуми: $O(n \log n)$ яки $O(n^2)$.
   • Тикшерү (линейлы эзләү): $O(n)$.
   • Гомуми: $O(n)$.
   • Бу очракта, тикшерү ($O(n)$) арзанрак, сортлау + эзләү ($O(n \log n)$ яки аннан да күбрәк).

2. Күп тапкыр эзләү массивында:

   • Әгәр $k$ эзләү бер үк массивта башкарылырга кирәк булса.
   • Беренче тапкыр сортлау: $O(n \log n)$ яки $O(n^2)$.
   • Сортлаганнан соң $k$ бинаралы эзләү: $k \times O(\log n) = O(k \log n)$.
   • Гомуми: $O(n \log n + k \log n)$ яки $O(n^2 + k \log n)$.
   • $k$ линейлы эзләү: $k \times O(n) = O(kn)$.
   • Гомуми: $O(kn)$.
   • Әгәр $k$ зур булса ($k > \log n$), сортлау һәм бинаралы эзләү арзанрак була: $O(n \log n + k \log n)$ каршы $O(kn)$.

3. Үзенчәлекле очраклар:

   • Әгәр массив инде өлешчә сортланган яки махсус структурасы бар икән, тизрәк алгоритмнар бар.
   • Хэш-таблицалар (Set яки Hash Rubyда) уртача $O(1)$ вакытта эзләү мөмкинлеген бирә, бу гадәттә сортлау яки линейлы эзләүдән тизрәк.

Нәтиҗә: Бер тапкыр эзләү өчен, линейлы эзләү арзанрак. Күп тапкыр эзләү өчен, сортлау белән бинаралы эзләү файдалырак була, әгәр эзләүләр саны җитәрлек зур булса. Тиз эзләү һәм мәгълүмат структурасы үзгәрә алса, Set яки Hash иң оптималь карар булачак.

Rubyда линейлы эзләү үрнәге:

# Элементны эзләү не сортланган массивта
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Беренче туры килгәнне табу өчен туктату
  end
end

puts found # => 8

Сортлау һәм бинаралы эзләү үрнәге Rubyда (стандарт методлар белән):

# Сортлау
array = [5, 2, 8, 1, 9, 4]
sorted_array = array.sort # $O(n \log n)$ Rubyда Timsort өчен

# Бинаралы эзләү (Rubyда 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 "Элемент табылмады"
end