Kirish Hozirgi dunyoda aloqa tarmog'i juda tez sur'atlar bilan kengayib bormoqda. Korxonalar boshqaruv samaradorligini oshirish uchun raqamli tizimga o'tishadi

Kirish
Hozirgi dunyoda aloqa tarmog'i juda tez sur'atlar bilan kengayib bormoqda. Korxonalar boshqaruv samaradorligini oshirish uchun raqamli tizimga o'tishadi. Internetda ishlab chiqarilgan ma'lumotlar miqdori ortib bormoqda va natijada ma'lumotlar to'plamlari murakkablashmoqda. Ma'lumotlarni diqqat bilan va samarali tarzda tartibga solish, boshqarish, kirish va tahlil qilish muhim, ma'lumotlar tuzilmasi eng foydali usul bo'lib, maqola unga qaratilgan.


ma'lumotlar tuzilishi.
Kompyuter fanida ma'lumotlar tuzilmalari mavhum ma'lumotlar turlari (ADT) uchun asos bo'lib xizmat qiladi, bu erda ADT ma'lumotlar turlarining mantiqiy shaklidir. Ma'lumotlar turlarining jismoniy dizayni ma'lumotlar tuzilmalari yordamida amalga oshiriladi. har xil turdagi ilovalar uchun ma'lumotlar tuzilmalarining har xil turlari qo'llaniladi; ba'zilari aniq vazifalarga ixtisoslashgan.

Ma'lumotlar tuzilmalari ma'lumotlar qiymatlari va ular o'rtasidagi munosabatlar, ma'lumotlarga tegishli funktsiyalar va operatsiyalar to'plami deb ataladi. Shunday qilib, foydalanuvchilar osongina ma'lumotlarga kirishlari va samarali o'zgartirishlari mumkin.

Ma'lumotlar tuzilmalari bizga katta ma'lumotlar bazalari kabi katta hajmdagi ma'lumotlarni boshqarishga yordam beradi. Samarali ma'lumotlar tuzilmalari samarali algoritmlar uchun asosiy asosdir. Samarali saqlashdan tashqari, ma'lumotlar tuzilmalari saqlangan joylardan ma'lumotlarni samarali olish uchun ham javobgardir. U massiv, Grafik, Qidiruv, Dasturlar, Bog'langan ro'yxat, Pointer, Stack, Navbat, Struktura, Saralash va boshqalarni o'z ichiga oladi.

Ma'lumotlar strukturasida qidirish tushunchalari, shuningdek, uning usullari ushbu maqolada yoritilgan.

Ma'lumotlar tuzilmasida qidirish nima?
Ma'lumotlar strukturasida qidirish deganda kompyuter xotirasida elementlar sifatida saqlangan elementlar to'plamidan kerakli ma'lumotlarni topish jarayoni tushuniladi. Ushbu elementlar to'plami massiv, bog'langan ro'yxat, grafik yoki daraxt kabi turli shakllarda bo'ladi. Ma'lumotlar tuzilmalarida qidirishni aniqlashning yana bir usuli - bu elementlar to'plamida o'ziga xos xususiyatlarning kerakli elementini joylashtirishdir.



Qidiruv usullari
Ma'lumotlar strukturasida qidirish, saqlangan ma'lumotlar strukturasining istalgan shaklidan elementni tekshirish yoki ajratib olish uchun qidiruv algoritmlarini qo'llash orqali amalga oshirilishi mumkin.

Ushbu algoritmlar qidiruv operatsiyasining turiga qarab tasniflanadi, masalan:

Ketma-ket qidiruv

To'plamning har bir komponentini tekshirishda elementlar ro'yxati yoki massivi ketma-ket o'tkaziladi.
Masalan - Lineer Search.

Intervalli qidiruv

Intervalli qidiruv saralangan ma'lumotlar tuzilmalarida qidirish uchun aniq mo'ljallangan algoritmlarni o'z ichiga oladi. Samaradorlik nuqtai nazaridan, bu algoritmlar chiziqli qidiruv algoritmlariga qaraganda ancha yaxshi.
Misol- Logarifmik qidiruv, Ikkilik qidiruv.
Ushbu usullar ma'lumotlar to'plamidagi qidiruv elementiga mos keladigan elementni qidirish uchun algoritm tomonidan sarflangan vaqt asosida baholanadi va quyidagilar tomonidan beriladi:

Eng yaxshi vaqt

O'rtacha vaqt
Eng yomon vaqt
Asosiy tashvishlar algoritm ishlashining kafolatlangan prognozlarini ta'minlaydigan eng yomon holatlar bilan bog'liq va o'rtacha vaqtdan ko'ra hisoblash osonroq.

Ushbu maqoladagi tushunchalar va misollarni ko'rsatish uchun biz har qanday ma'lumot formatidagi ma'lumotlar to'plamidagi "n" elementlarini qabul qilamiz. Tahlil va algoritmni taqqoslashni osonlashtirish uchun dominant operatsiyalar qo'llaniladi. Taqqoslash ma'lumotlar tuzilmasida qidirish uchun dominant operatsiya bo'lib, O() bilan belgilanadi va "katta-Oh" yoki "Oh" deb talaffuz qilinadi.

Ma'lumotlar strukturasida chiziqli qidiruv, ikkilik qidiruv, interpolyatsiya qidiruvi, pastki ro'yxat qidirish, eksponensial qidiruv, o'tish qidiruvi, Fibonachchi qidiruvi, hamma joyda mavjud ikkilik qidiruv, pastki qator qidirish uchun rekursiv funksiya, cheklanmagan, ikkilik qidiruv va rekursiv kabi ko'plab qidiruv algoritmlari mavjud. berilgan massivda elementni chiziqli izlash dasturi. Maqolada chiziqli qidiruv, ikkilik qidiruv va interpolyatsiya qidiruv algoritmlari va ularning ishlash tamoyillari mavjud.

Keling, ma'lumotlar strukturasidagi chiziqli va ikkilik qidiruvlarni batafsil ko'rib chiqaylik.

chiziqli qidiruv.
Chiziqli qidiruv algoritmi massivning barcha elementlarini iterativ tarzda qidiradi. U bittaning eng yaxshi bajarilish vaqtiga va n ning eng yomon bajarilish vaqtiga ega, bu erda n - qidiruv massividagi elementlarning umumiy soni.

Bu ma'lumotlar tuzilmasidagi eng oddiy qidiruv algoritmi bo'lib, elementlar to'plamidagi har bir elementni ma'lumotlar yig'ish oxirigacha qidirilayotgan elementga mos kelguncha tekshiradi. Berilgan ma'lumotlar saralanmagan bo'lsa, boshqa qidiruv algoritmlariga nisbatan chiziqli qidiruv algoritmi afzalroqdir.

Chiziqli qidiruvdagi murakkabliklar quyida keltirilgan:

Kosmik murakkablik:

Chiziqli qidiruv qo'shimcha joy ishlatmaganligi sababli, uning fazoviy murakkabligi O(n), bu erda n - massivdagi elementlar soni.

Vaqtning murakkabligi:

Eng yaxshi holat murakkabligi = O(1) qidirilayotgan element qidiruv massivining birinchi elementida mavjud bo'lganda yuzaga keladi.

Eng yomon murakkablik = O(n) talab qilinadigan element massivning oxirida joylashgan yoki umuman mavjud bo'lmaganda yuzaga keladi.
O'rtacha ish murakkabligi = o'rtacha holat izlanadigan element massivning o'rtasida joylashganida sodir bo'ladi.
Chiziqli qidiruv algoritmi uchun psevdokod