Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti dasturiy injinering fakulteti Dasturiy Ta’minot Tizimlarini Loyihalash Mavzu: Dastur loyihasi va uning samaradorligi

Algoritmning ishlashi

• Algoritmning ishlashi
• Agar ketma-ket qidiruvni binar qidiruvga o'zgartirsak nima bo'ladi? Binar qidiruv O(log2n) vaqtini ko'rsatadi, bu katta n uchun O(n) dan sezilarli darajada tezroq. Masalan, n=10 uchun chiziqli qidiruv 10 vaqt birligini oladi, ikkilik qidiruv esa taxminan 4,3 vaqt birligini oladi. Biroq, n = 1000 bo'lsa, ikkilik qidiruv faqat 11 vaqt birligini oladi! Binar qidiruvni amalga oshirish bilan bog'liq mumkin bo'lgan muammo shundaki, qidirilayotgan qiymatlar tartiblangan bo'lishi kerak. Binar qidiruvga o'tish haqidagi savolga javob berish uchun har bir dasturlash tilini ko'rib chiqish kerak.
• Python roʻyxati maʼlumotlar strukturasi indekslashni qoʻllab-quvvatlaydi ([ ] operatori yordamida) va roʻyxat tarkibini joyida tartiblovchi saralash usuliga ega (yaʼni, saralashni amalga oshirish uchun qoʻshimcha xotiradan foydalanmaydi)
• Python shuningdek, tarkibni yangi ro'yxat ob'ektiga saralaydigan tartiblangan deb nomlangan o'rnatilgan funksiyaga ega. Indekslash operatori doimiy vaqt O(1) unumdorligini namoyish etadi, shu bilan birga tartiblash usuli ham, sorted() funksiyasi ham O(nlogn) vaqt unumdorligiga ega oshirish uchun qoʻshimcha xotiradan foydalanmaydi).

• Python ro'yxatlari bilan biz birinchi navbatda kontakt nomi ABAda bor yoki yo'qligini bilish uchun ikkilik qidiruvni amalga oshiramiz. Bu O( log2n) vaqt ishlashiga ega bo'ladi. Agar kontakt nomi ABAda bo'lmasa, biz yangi kontakt nomini ro'yxat ma'lumotlar strukturasining oxiriga qo'shamiz (doimiy vaqt O(1) ishlashi) va keyin ro'yxatni (O(n logn) ishlashi bilan) saralaymiz, ya’ni keyingi binar qidiruvning to'g'ri ishlashini ta’minlashi uchun.

Java ArrayList ma'lumotlar strukturasi indekslashni (get usuli yordamida) qo'llab-quvvatlaydi va Java Collections sinfida