Algoritmlar bilan ishlashni endi boshlaganlarida tug'iladigan klassik savol:
Sort qilinmagan arrayda biror elementni izlash O(n) vaqt talab qiladi.
Sort qilingan arrayda esa qidiruv O(log n), lekin sort qilishning o'zi O(n * log n) vaqt oladi. Demak, arrayni sort qilib, elementni izlash sort qilinmagan arraydagi qidiruvdan ko'ra ko'p vaqt oladi. Unda sort qilishning nima keragi bor?

Javob: Sort qilinmagan arrayda har bir search uchun O(n) sarflanadi. Sort qilingan arrayda esa sort qilish uchun esa O(n * log n), keyingi har bir search uchun O(log n) vaqt sarflanadi. Bir martalik operatsiya uchun sort qilmasdan qidirish tezroq bo'lsa-da, umumiy m ta (m >> n) qidiruv uchun sort qilmasdan qidirish O(m * n), sort qilib, keyin qidirish esa O(m * log n) vaqt talab qiladi.
Xulosa qilganda, kelajakdagi qidiruvlarni ham hisobga olganda, arrayni tartiblash foydali.

P.S. Bu savolni yaqinda bir guruhda ko'rgandim, bugun bir kishi shaxsiyda shu savolni so'rabdi. Kimgadir foydali bo'lsa, xursand bo'laman.