Nima arzonroq: massivni tartiblash va keyin qidirish…

Kontextga bog'liq.

Bir marta qidirish noto'g'ri tartiblangan massivda:
- Tartiblash: Tartiblashning murakkabligi odatda $O(n \log n)$ yoki $O(n^2)$ (algoritmga bog'liq).
- Qidirish (tartibdan so'ng binar): $O(\log n)$.
- Umumiy: $O(n \log n)$ yoki $O(n^2)$.
- ```
Chiziqli qidirish (yurish): $O(n)$.
```
- ```
Umumiy: $O(n)$.
```
- Bu holda, yurish ($O(n)$) tartiblash + qidirish ($O(n \log n)$ yoki undan ko'proq) dan arzonroq.
Bir nechta qidirish massivida:
- Agar siz bir xil massivda $k$ ta qidirishni amalga oshirishingiz kerak bo'lsa.
- Bir marta tartiblash: $O(n \log n)$ yoki $O(n^2)$.
- Tartiblashdan so'ng $k$ ta binar qidirishni bajarish: $k \times O(\log n) = O(k \log n)$.
- Umumiy: $O(n \log n + k \log n)$ yoki $O(n^2 + k \log n)$.
- $k$ ta chiziqli yurishni bajarish: $k \times O(n) = O(kn)$.
- Umumiy: $O(kn)$.
- Katta $k$ uchun ($k > \log n$), tartiblash va binar qidirish arzonroq bo'ladi: $O(n \log n + k \log n)$ qarshi $O(kn)$.
Maxsus holatlar:
- Agar massiv allaqachon qisman tartiblangan yoki maxsus tuzilishga ega bo'lsa, yanada tezroq tartiblash yoki qidirish algoritmlari mavjud.
- Hash-jadvallar (Set yoki Hash Rubyda) o'rtacha $O(1)$ vaqtni taklif qiladi va odatda tartiblash yoki chiziqli qidirishdan tezroq.

Xulosa: Bir martalik qidirish uchun yurish arzonroq. Bir xil massivda ko'p marta qidirish uchun, tartiblash va binar qidirish etarlicha ko'p qidirish bilan foydali bo'ladi. Qidirish tezligi muhim bo'lsa va ma'lumotlar tuzilmasi o'zgartirilishi mumkin bo'lsa, Set yoki Hashdan foydalanish eng optimal yechim bo'lishi mumkin.

Ruby'da chiziqli qidirish misoli:

# Noto'g'ri tartiblangan massivda element qidirish
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Birinchi moslik topilgach to'xtash
  end
end

puts found # => 8

Ruby'da tartiblash va binar qidirish misoli (standart metodlardan foydalanib):

# Tartiblash
array = [5, 2, 8, 1, 9, 4]
sorted_array = array.sort # O(n \log n) Ruby'da Timsort

# Binar qidirish (Rubyda 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 "Element topilmadi"
end

Nima arzonroq: massivni tartiblash va keyin qidirish yoki elementni topish uchun o'tish usulidan foydalanish?