Reja: kirish I. Bob. Saralash algoritimi haqida tushuncha

I.BOB.Saralash algoritimi haqida tushuncha.
Saralash haqida tushuncha va algoritmlari
Saralash deganda buyumlarni ba'zi bir mezonlarga ko'ra tartiblash tushuniladi. Ko'pincha, raqamli qator haqida gap ketganda, saralash bitning o'sish tartibida joylashishini anglatadi. Agar ular mag'lubiyat ma'lumotlari shaklida bo'lsa, unda, odatda, leksikografik tartib ishlatiladi (raqamli belgilar kodiga muvofiq ortib boradi). Kompozit (tizimli) ma'lumotlarga buyurtma berish ko'pincha murakkabroq taqqoslash tartiblarini talab qiladi. Tartiblash ma'lumotlarni qayta ishlash algoritmlarining eng muhim sinfiga kiradi va juda ko'p usullar bilan amalga oshiriladi. Bu voqealarni bir-biri bilan har xil mezonlardan foydalanib taqqoslash mumkin: jarayon vaqti, xotirani egallash, amalga oshirishning murakkabligi, har xil turdagi ma'lumotlarga ustunlik va boshqalar. Hozirda o'nlab xil saralash usullari mavjud va doimiy ravishda yangi usullar paydo bo'lmoqda, ular ko'pincha mavjud bo'lgan va takomillashtirish maqsadida paydo bo'ladigan variantlardir. Saralash algoritmlarini bir-biri bilan taqqoslash mumkin bo'lgan eng muhim o'lchov bu hisoblashning murakkabligi.
Hisoblashning murakkabligi - bu informatika va algoritm nazariyasining algoritmning ishlash vaqtining kirish ma'lumotlari hajmiga bog'liqligini ko'rsatadigan tushuncha. Bunday funktsiyani tavsiflash uchun "O" bosh harfidan foydalaning. Funktsiyaning o'zi, masalan, chiziqli O (N), kvadratik O (N2), logarifmik O (log N) bo'lishi mumkin, bu erda N - bu massivning kattaligi. Shuni ta'kidlash kerakki, hisoblashning murakkabligini baholash asimptotik indikator bo'lib, saralangan massivning kattaligi cheksizlikka intilganda qo'llaniladi. Bu sizga bajarilish vaqtini taxmin qilish va turli algoritmlarning ishlash ko'rsatkichlarini bir-biri bilan taqqoslash imkonini beradi. Haqiqiy hajmdagi ma'lumotlar bilan ushbu hisob-kitobni aniq hisob-kitoblar uchun ishlatib bo'lmaydi. Ko'p algoritmlar xotira hajmi va tezligi o'rtasida tanlov taklif qiladi. Muammoni tezda, katta hajmdagi xotiradan yoki sekinroq, kamroqdan foydalangan holda hal qilish mumkin. Turli xil algoritmlarni taqqoslashda sarflangan resurslar miqdori (xotira hajmi va bajarish vaqti) qanday qilib kirish ma'lumotlari miqdoriga bog'liqligini bilish muhimdir. Masalan, bitta usul bilan saralashda o'n ming sonni qayta ishlash 1 soniyani, million raqamni qayta ishlashni 10 soniyani oladi, boshqa algoritmdan foydalanganda mos ravishda ikki va besh soniyani olishi mumkin. Bunday sharoitda qaysi algoritm yaxshiroq ekanligini aniq aytish mumkin emas, shuning uchun qanday qilib har bir hisoblash moslamasi hisoblash muddatiga ta'sir qilishi mumkin bo'lgan o'ziga xos xususiyatlarga ega. Odatda, algoritmni ishlab chiqishda ba'zi texnik tafsilotlar, masalan, protsessor keshining hajmi, operatsion tizim tomonidan amalga oshiriladigan ko'p vazifalarni bajarish turi va boshqalar hisobga olinmaydi. dasturning bajarilish jarayoniga ta'sir qiluvchi ko'plab texnik omillar mavjud bo'lganligi sababli har safar har xil bajarilish vaqti. Shunday qilib, algoritmlarning samaradorligini bir-biri bilan taqqoslash usuli matematik muammo, ammo texnik emasligini aniqlashtirish kerak. Algoritmlarni tahlil qilish xotiraga (RAM) tasodifiy kirish imkoniga ega bo'lgan mashina deb nomlangan mavhum modelda amalga oshiriladi. Model quyidagicha ishlaydigan xotira va protsessordan iborat:
1. Xotira har birida manzilga ega bo'lgan va bitta ma'lumot elementini saqlashi mumkin bo'lgan hujayralardan iborat. 2. Xotiraga har bir kirish manzil qilingan katakchaning sonidan qat'i nazar, bitta vaqt birligini oladi. 3. Xotira hajmi har qanday algoritm-ritmni amalga oshirish uchun etarli. 4. Protsessor har qanday elementar operatsiyani (masalan, asosiy mantiqiy va arifmetik amallar, xotiradan o'qish, xotiraga yozish, subroutinni chaqirish va hk) bir vaqtning o'zida amalga oshiradi. 5. Looplar va funktsiyalar elementar amallar hisoblanmaydi. Ushbu model haqiqiy kompyuterdan uzoqroq, ammo algoritmlarning vaqt murakkabligini tahlil qilish uchun juda yaxshi. Algoritmlarning ikkita asosiy klassi mavjud: takrorlash algoritmlari va rekursiv algoritmlar. Takrorlash algoritmlari tsikl va shartli gaplarga asoslanadi. Ushbu sinf algoritmlarini tahlil qilish ulardagi barcha tsikllarni va amallarni hisoblashni talab qiladi. Rekursiv algoritmlar matematik rekursiv funktsiya tushunchasiga asoslangan. Dasturlash tillarida rekursiv funktsiya - bu o'ziga murojaat qiladigan funktsiya dasturi. Rekursiv dastur o'zini abadiy chaqira olmaydi, shuning uchun rekursiv dasturning ikkinchi muhim xususiyati bu dasturning o'zi qo'ng'iroq qilishni to'xtatishiga imkon beradigan tugatish shartining mavjudligi. Rekursiv algoritmni tahlil qilish odatda ancha qiyin. Bu rekursiyani yakunlash shartini bajarishdan oldin rekursiv funktsiyani chaqirish operatsiyalari sonini sub-hisoblashni va har bir chaqirilgan recursive funktsiya ichidagi operatsiyalarni sanashni talab qiladi.
7 Saralashni tahlil qilishda muhim savol bu operatsiyalarni hisobga olish masalasidir: qaysi operatsiyalar boshlang'ich hisoblanadi, qaysilari yo'q? Albatta, bu savolga aniq va aniq javob berish juda qiyin, ammo faqat eng muhim operatsiyalarni sanash zarurligi to'g'risida ma'lum bir kelishuv mavjud. Informatika fanida ular ko'pincha quyidagi operatsiyalarni o'z ichiga oladi: 1) oddiy topshiriq: a = b; 2) massiv elementini indekslash; 3) arifmetik amallar: -, +, *, /; 4) taqqoslash operatsiyalari: <,>, ==, <=,> = ,! =; 5) mantiqiy operatsiyalar: yoki, va, emas. Algoritmning vaqt murakkabligiga kirish ma'lumotlarining miqdori sezilarli darajada ta'sir qiladi. Shunday qilib, agar kichik hajmdagi ma'lumotlarni qayta ishlashda ikki xil algoritmlarning ishlash vaqti o'rtasidagi farq ahamiyatsiz bo'lsa, unda bu hajmning oshishi ularning har birining bajarilish vaqtiga sezilarli ta'sir ko'rsatishi mumkin. Algoritmni bajarish tezligi nafaqat kirish hajmiga, balki ma'lumotlar qiymatlariga ham bog'liq bo'lishi mumkin. Tanlangan ma'lumotlar tarkibida allaqachon o'z pozitsiyalarini muvaffaqiyatli egallab turgan ma'lumotlar mavjud. Masalan, ko'plab saralash algoritmlari allaqachon tartiblangan yoki qisman tartiblangan bo'lsa, massivga buyurtma berish uchun juda kam vaqt sarflaydi. Shu sababli, algoritmlarning vaqt murakkabligini baholash uchta holatda amalga oshiriladi: eng yomon, eng yaxshi va o'rtacha. Algoritm muammoni hal qilish uchun maksimal miqdordagi elementar operatsiyalarni bajarishi kerak bo'lgan eng yomon holat, kirish ma'lumotlarining eng muvaffaqiyatli to'plamiga to'g'ri keladi. Eng yaxshi holatda, kiritilgan ma'lumotlar to'plami operatsiyalarning mumkin bo'lgan minimal sonini kafolatlaydi. O'rta ishni aniqlash ancha qiyin.