Samarqand davlat universiteti raqamli texnologiyalar fakulteti dasturiy injiniring yo

Algoritm	Ma’lumotlar tuzilmasi	Vaqt bo’yicha murakkabligi
Qo’shimcha ma’lumotlar
		Yaxshi	O’rta	Yomon	Yomon holatda
Tezkor saralash	Massiv	O(n log(n))	O(n log(n))	O(n^2)	O(n)
Surish orqali saralash	Massiv	O(n log(n))	O(n log(n))	O(n log(n))	O(n)
Piramidali saralash	Massiv	O(n log(n))	O(n log(n))	O(n log(n))	O(1)
Pufakchali saralash	Massiv	O(n)	O(n^2)	O(n^2)	O(1)
Qo’yish orqali saralash	Massiv	O(n)	O(n^2)	O(n^2)	O(1)
Tanlash orqali saralash	Massiv	O(n^2)	O(n^2)	O(n^2)	O(1)
Blokli saralash	Massiv	O(n+k)	O(n+k)	O(n^2)	O(nk)
Razryad bo’yicha saralash	Massiv	O(nk)	O(nk)	O(nk)	O(n+k)

4.TOPSHIRIQ

1 – topshiriq.
Berilgan variant bo’yicha C++ (Python, Java) tilida har uchala saralash metodini bajaring va jadval shaklida solishtirib analiz qiling.
Birinchi topshiriq bo’yicha variantlar

Ro’yhat bo’yicha variant nomeri	Massivni to’ldirish	Saralash metodi	Har bir metod uchun massivdagi elementlarning soni
1,2,3	Tasodifiy elementlar bilan to’ldirilgan massiv	Sanash Pufakchali Shell	300	1200	4000
4,5,6	Tasodifiy elementlar bilan to’ldirilgan massiv	Surish Tezkor Tanlash	400	1300	4500
7,8,9	Tasodifiy elementlar bilan to’ldirilgan massiv	Pufakchali Tezkor Kiritish	200	1500	4000
10,11,12	Tasodifiy elementlar bilan to’ldirilgan massiv	Surish Sheyker Tezkor	500	1600	5000
13,14,15	Tasodifiy elementlar bilan to’ldirilgan massiv	O’rniga qo’yish Pufakchali Tanlash	350	2000	6000
16,17,18	Tasodifiy elementlar bilan to’ldirilgan massiv	Sheyker Tezkor Surish	450	1800	5500

2 – topshiriq
C++ (Python, Java) tilida quyida keltirilgan amallarni bajargan holda ustuvor navbat tashkil qiling:

• 
  Berilgan N ta elementdan iborat ustuvor navbat hosil qiling;
  
• 
  Yangi element qo’shing;
  
• 
  Eng katta elementni yechib oling;
  
• 
  Berilgan qandaydir elementning prioritetini o’zgartiring;
  
• 
  Berilgan qandaydir elementni yechib oling;
  
• 
  Ikkita ustuvor navbatni birlashtiring.
  

Algoritm - bu belgilaydigan cheklangan qoidalar toʻplami, muayyan vazifalar toʻplamini hal qilish boʻyicha amallar ketma-ketligi va beshta muhim xossaga ega: aniqlik, tushunarlilik, kiritish, chiqarish, samaradorlik Algoritm qadami – Algoritmda bajarilishi tugallangan amallar ketmaketligi. Algoritmning vaqt boʻyicha qiyinligi – Algoritm sarflanayotgan vaqt masalaning oʻlchami funksiyasi deyiladi.
Algoritmlarning murakkabligini tahlil qilish. Misollar
01/06/2015 algoritmlar
Algoritm - bu o'zgaruvchan boshlang'ich ma'lumotlardan kerakli natijaga olib keladigan hisoblash jarayonini noyob tarzda belgilaydigan aniq retseptdir.
Algoritmlarni ishlab chiqishda hisob-kitoblarni amalga oshirish uchun zarur bo'lgan resurslarni baholay olish juda muhim, baholash natijasi murakkablik (mehnat sarfi) funktsiyasidir. Hisoblangan resurs ko'pincha protsessor vaqti (hisoblash murakkabligi) va xotira (algoritmning xotira murakkabligi) hisoblanadi. Baholash bajarilish vaqtini bashorat qilish va algoritmlarning ish faoliyatini solishtirish imkonini beradi.
Tarkib:
RAM modeli (tasodifiy kirish mashinasi)
Hisoblash operatsiyalari. Kirish sinflari
Asimptotik belgi
Algoritm tahliliga misollar
Algoritmlarni tahlil qilish uchun matematik apparat
Xulosa formulalari
Xulosa va integratsiya
Algoritmlarning murakkabligini taqqoslash. chegaralar
Logarifmlar va algoritmlarning murakkabligi
Tahlil natijalari. Izohlar. Adabiyot
RAM modeli (tasodifiy kirish mashinasi)
Har bir hisoblash qurilmasi o'ziga xos xususiyatlarga ega bo'lib, bu hisoblash davomiyligiga ta'sir qilishi mumkin. Odatda algoritmni loyihalashda protsessor keshining hajmi yoki operatsion tizim tomonidan amalga oshirilgan ko'p vazifalar turi kabi tafsilotlar hisobga olinmaydi. Algoritmlarni tahlil qilish tasodifiy xotira (RAM) mashinasi deb ataladigan mavhum kompyuter modelida amalga oshiriladi.
Model xotira va protsessordan iborat bo'lib, ular quyidagicha ishlaydi:
xotira hujayralardan iborat bo'lib, ularning har biri manzilga ega va ma'lumotlarning bir elementini saqlashi mumkin;
har bir xotiraga kirish manzillangan yacheykaning sonidan qat'iy nazar bir birlik vaqtni oladi;
xotira miqdori har qanday algoritmni bajarish uchun etarli;
protsessor har qanday elementar amalni (asosiy mantiqiy va arifmetik amallar, xotiradan o‘qish, xotiraga yozish, kichik dasturni chaqirish va h.k.) bir vaqtning o‘zida bajaradi;
sikl va funksiyalar elementar amallar hisoblanmaydi.
Bunday model haqiqiy kompyuterdan uzoq bo'lishiga qaramay, u algoritmlarni tahlil qilish uchun juda mos keladi. Algoritm ma'lum bir kompyuter uchun amalga oshirilgandan so'ng, siz profillash va past darajadagi optimallashtirishni amalga oshirishingiz mumkin, ammo bu algoritmni optimallashtirish emas, balki kodni optimallashtirish bo'ladi.
Hisoblash operatsiyalari. Kirish sinflari
Murakkablikni baholashning bir usuli ([Math Processing Error]) bajarilgan operatsiyalar sonini hisoblashdir. Masalan, massivning minimal elementini topish algoritmini ko'rib chiqing.
Boshlash; N elementli massivning minimal elementini topish
min := massiv[1]
i uchun 2 dan N gacha:
agar massiv[i] < min
min := massiv[i]
nihoya; qaytish min
Ushbu algoritmni bajarishda quyidagilar amalga oshiriladi:
N — 1 sikl hisoblagichiga yangi qiymat berish operatsiyasi i;
N - N qiymati bilan 1 hisoblagich taqqoslash operatsiyasi;
N — massiv elementlarini min qiymati bilan solishtirishning 1 operatsiyasi;
1 dan N gacha o'zgaruvchiga qiymat berish operatsiyalari min.
Amaliyotlarning aniq soni qayta ishlanayotgan ma'lumotlarga bog'liq bo'ladi, shuning uchun eng yaxshi, eng yomon va o'rtacha holatlar haqida gapirish mantiqan. Shu bilan birga, har doim eng yomon holatga alohida e'tibor qaratiladi, shu jumladan "yomon" ma'lumotlar tajovuzkor tomonidan ataylab kirishga yuborilishi mumkin.
O'rtacha holat tushunchasi ma'lumotlar to'plamining bir xil ehtimoli borligini taxmin qilgan holda algoritmning harakatini baholash uchun ishlatiladi. Biroq, bunday baholash ancha murakkab:
bir guruhning har qanday ma'lumotlar to'plami uchun algoritmning murakkabligi ([Math Processing Error]) bir xil bo'lishi uchun dastlabki ma'lumotlar guruhlarga bo'linadi;
to'plamlarning umumiy sonidagi guruh ma'lumotlar to'plamining ulushiga asoslanib, har bir guruh uchun ehtimollik hisoblanadi ([Math Processing Error]);
o'rtacha ish ball quyidagi formula bo'yicha hisoblanadi: [Math Processing Error].
Asimptotik belgi
Amallar sonini hisoblash algoritmlarning samaradorligini solishtirish imkonini beradi. Biroq, shunga o'xshash natijani oddiyroq usulda olish mumkin. Tahlil qayta ishlangan ma'lumotlarning etarlicha katta hajmini ([Math Processing Error]) kutish bilan amalga oshiriladi, shuning uchun operatsiyalarning aniq soni emas, balki murakkablik funktsiyasining o'sish tezligi muhim ahamiyatga ega.
O'sish sur'atini tahlil qilishda ifodadagi doimiy shartlar va omillar e'tiborga olinmaydi, ya'ni. [Math Processing Error] va [Math Processing Error] funktsiyalari o'sish tezligi bo'yicha ekvivalentdir. Muhim bo'lmagan a'zolar faqat "to'lqinlilik" ni qo'shadi, bu esa tahlilni murakkablashtiradi.
Algoritmlarni baholashda quyidagi funktsiyalar sinflarini aniqlaydigan maxsus asimptotik belgilar qo'llaniladi:
[Math Processing Error] - funktsiyalar g dan sekinroq o'sadi;
[Math Processing Error] - funksiyalar g dan tezroq o'sadi;
[Math Processing Error] - funktsiyalar g bilan bir xil tezlikda o'sadi.
[Math Processing Error] yozuvi f funksiyasi [Math Processing Error] sinfiga tegishli ekanligini bildiradi, ya'ni. f funktsiyasi yuqoridan argumentning etarlicha katta qiymatlari uchun g funktsiyasi bilan chegaralangan. [Matematik ishlov berish xatosi].
g funksiyani pastdan f funksiya bilan chegaralanishi quyidagicha yoziladi: [Math Processing Error]. [Math Processing Error] va [Math Processing Error] belgilari bir-birini almashtiradi: [Math Processing Error]. asimptotik belgi_Omega "Katta O" va "Katta Omega" asimptotik belgilari.
Agar f va g funktsiyalari bir xil o'sish tezligiga ega bo'lsa ([Matematik ishlov berish xatosi]), u holda [Math Processing Error] va [Math Processing Error] musbat konstantalar mavjud bo'lib, [Math Processing Error]. Bu bilan [Matematik ishlov berish xatosi].

asimptotik notation_Theta

"Theta big" asimptotik belgisi
Algoritm tahliliga misollar
Yuqorida keltirilgan massivning minimal elementini topish algoritmi siklning N ta takrorini bajaradi. Har bir iteratsiyaning murakkabligi massiv elementlari soniga bog'liq emas, shuning uchun u [Math Processing Error] murakkabligiga ega. Shu munosabat bilan butun algoritmning yuqori chegarasi [Math Processing Error] hisoblanadi. Xuddi shunday, pastroq murakkablik bahosi hisoblab chiqiladi va u yuqoriga to'g'ri kelishi sababli, biz [Math Processing Error] ni tasdiqlashimiz mumkin.
Pufakchali tartiblash algoritmi ikkita ichki o'rnatilgan halqadan foydalanadi. Ichki juft elementlarda ketma-ket taqqoslanadi va agar elementlar noto'g'ri tartibda ekanligi aniqlansa, almashtirish amalga oshiriladi. Tashqi sikl massivda kerakli tartibni buzadigan kamida bitta juft elementlar mavjud bo'lguncha bajariladi [2].
Boshlash; N ta elementdan iborat pufakchali tartiblash massivi
nPairs := N; juft elementlar soni
hasSwapped := false; hozirgacha hech bir er-xotin qoidalarni buzmagan
1 dan nPairs-1 gacha bo'lgan barcha i uchun:
agar massiv[i] > massiv[i+1] bo'lsa, unda: almashtirish(massiv[i], massiv[i+1]); elementlarni almashtirish
hasSwapped := true; almashtirish topildi
nPairs := nPairs - 1; eng katta element oxirida joylashtirilishi kafolatlanadi
agar hasSwapped = true - keyin 3-bosqichga o'ting
nihoya; massiv tartiblangan
Almashtirish funktsiyasining murakkabligi massivdagi elementlar soniga bog'liq emas, shuning uchun u [Math Processing Error] sifatida baholanadi. Ichki tsiklning bajarilishi natijasida eng katta element tartiblanmagan qism massivining oxiriga siljiydi, shuning uchun N ta bunday chaqiruvdan keyin massiv baribir tartiblanadi. Agar massiv tartiblangan bo'lsa, ichki tsikl faqat bir marta bajariladi.
Shunday qilib:
[Matematik ishlov berish xatosi];
[Matematik ishlov berish xatosi].
Tanlovni saralash algoritmida massiv aqliy jihatdan tartiblangan va xom qismlarga bo'linadi. Har bir bosqichda massivning tartiblanmagan qismidan minimal element tanlanadi va tartiblangan qismga qo'shiladi [2].
Boshlash; tanlash_sort - N elementli massivni tanlash usuli bo'yicha saralash
1 dan N gacha bo'lgan barcha i uchun:
imin := indMin(massiv, N, i)
almashtirish (massiv [i], massiv [imin])
nihoya; massiv tartiblangan
Massivning tartiblanmagan qismining eng kichik elementini topish uchun massivni, massivning o‘lchamini va izlash uchun joy raqamini oladigan indMin funksiyasidan foydalaniladi. Bu funksiyaning murakkabligini tahlil qilish min funksiya uchun bajarilgani kabi amalga oshirilishi mumkin - amallar soni qayta ishlangan elementlar soniga chiziqli bog'liq: [Math Processing Error].
Tanlash algoritmining eng oddiy holati - bu minimal (yoki maksimal) elementni ro'yxat bo'ylab takrorlash orqali topish, ishlaydigan minimal - hozirgacha minimal - (yoki maksimal) ko'rsatkichlarini kuzatib borish va tanlov saralash bilan bog'liq deb ko'rish mumkin. Aksincha, tanlov algoritmining eng qiyin holati bu mediani topishdir. Aslida, medianlar medianasida bo'lgani kabi, umumiy tanlov algoritmini tuzishda ixtisoslashgan median-tanlov algoritmidan foydalanish mumkin. Tanlovning eng taniqli algoritmi Quickselect bo'lib, u Quicksort bilan bog'liq; Quicksort singari, u o'rtacha (asimptotik) maqbul o'rtacha ko'rsatkichga ega, ammo eng yomon ko'rsatkichlar, ammo uni eng yomon ko'rsatkichlarni ham berish uchun o'zgartirish mumkin.
Ro'yxat yoki qatorni saralash orqali kerakli elementni tanlab, saralashga saralashgacha qisqartirish mumkin. Ushbu usul bitta elementni tanlash uchun samarasiz, ammo massivdan ko'plab tanlovlarni o'tkazish kerak bo'lganda samarali bo'ladi, bu holda faqat bitta boshlang'ich, qimmat saralash kerak bo'ladi, undan keyin ko'plab arzon tanlov operatsiyalari - massiv uchun O (1) , tasodifiy kirishning etishmasligi sababli, saralangan bo'lsa ham, bog'langan ro'yxatda tanlov O (n) bo'lsa ham. Umuman olganda, saralash uchun O (n log n) vaqt kerak bo'ladi, bu erda n - ro'yxatning uzunligi, ammo pastki chegara radiaks sort va count sort kabi taqqoslanmagan tartiblash algoritmlari bilan mumkin bo'lsa ham.
Butun ro'yxatni yoki qatorni saralash o'rniga, eng kichik yoki k kattaroq elementlarni tanlash uchun qisman saralashdan foydalanish mumkin. Keyinchalik kichkina k (eng katta element), qisman tartiblangan ro'yxatning eng kattasi (resp., Eng kichik element) - bu O (1) qatorga kirish uchun va O (k) - ro'yxatga kirish uchun
Tartibsiz qisman saralash
Agar qisman saralash eng kichik k elementlar qaytarilishi uchun yumshatilsa, lekin tartibda bo'lmasa, O (k log k) omilini yo'q qilish mumkin. Qo'shimcha maksimal tanlov (O (k) vaqtni olish) talab qilinadi, ammo {\ displaystyle k \ leq n} k \ leq n bo'lgani uchun, bu hali ham O (n) ning asimptotik murakkabligini keltirib chiqaradi. Darhaqiqat, bo'linishga asoslangan tanlash algoritmlari k-chi elementning o'zi va k-ning eng kichik elementlarini oladi (boshqa elementlar tartibda emas). Buni O (n) vaqt ichida amalga oshirish mumkin - Quickselectning o'rtacha murakkabligi va eng yomon holatdagi murakkab bo'linmalarga asoslangan tanlash algoritmlari.
Aksincha, tanlash algoritmini hisobga olgan holda, ro'yxatni takrorlash va k elementidan kam bo'lgan barcha elementlarni yozish orqali O (n) vaqt ichida tartibsiz qisman saralashni (k kichik elementlar, tartibda emas) osongina olish mumkin. Agar bu k - 1 dan kam elementga olib keladigan bo'lsa, qolgan elementlar k elementiga tenglashadi. Elementlarning tengligi ehtimoli tufayli ehtiyot bo'lish kerak: k elementga teng yoki teng bo'lmagan barcha elementlarni o'z ichiga olmaydi, chunki k elementdan kattaroq elementlar ham unga teng bo'lishi mumkin.
Shunday qilib tartibsiz qisman saralash (eng past k elementlar, lekin buyurtma qilinmagan) va k elementni tanlash juda o'xshash muammolar. Ular nafaqat bir xil asimptotik murakkablikka ega (O (n)), balki ikkalasining ham echimini boshqasiga to'g'ridan-to'g'ri algoritm (max k elementlarini topish yoki ro'yxatning elementlarini filtrlash) yordamida hal qilish mumkin. k-element qiymatining kesilishi).