|
Qisman tanlov saralash
Qisman saralash orqali tanlashning oddiy misoli bu qisman tanlash saralashidan foydalanishdir.
Minimal (maksimal maksimal) ni topish uchun aniq chiziqli vaqt algoritmi - ro'yxat bo'yicha takrorlash va shu paytgacha minimal (maksimal maksimal) elementni kuzatib borish - 1 ta eng kichik elementni tanlaydigan qisman tanlov saralashi sifatida qaralishi mumkin. Shu bilan birga, boshqa ko'plab qisman navlar, shuningdek, k = 1 holati uchun ushbu algoritmni qisqartiradi, masalan, qisman yig'ma tartiblash.
Umuman olganda qisman tanlov saralashi O (kn) vaqtni talab qiladigan oddiy tanlov algoritmini beradi. Bu asimptotik jihatdan samarasiz, ammo agar k kichik bo'lsa va uni bajarish oson bo'lsa, etarli darajada samarali bo'lishi mumkin. Aniq qilib aytganda, biz minimal qiymatni topamiz va uni boshiga o'tkazamiz, qolgan elementlarni k elementlar yig'ilguncha takrorlaymiz va keyin k elementni qaytaramiz. Qisman tanlov asosida saralash algoritmi:
function select(list[1..n], k)
for i from 1 to k
minIndex = i
minValue = list[i]
for j from i+1 to n do
if list[j] < minValue then
minIndex = j
minValue = list[j]
swap list[i] and list[minIndex]
return list[k]
Algoritmni tahlil qilishdan maqsad – algoritmga ma’lumotlarni aniq
muvaffaqiyatli qayta ishlash uchun kerak bo’ladigan xotira hajmi va ishlash
vaqtining baholari va chegaralarini olish. Bir masalani yechadigan ikki algoritmni
taqqoslash uchun qandaydirsonli mezon topish kerak.
Faraz qilaylik, A – qandaydir bir turkumdagi masalalarni yechadigan algoritm, n –
esa shu turkumdagi alohida bir masalaning kattaligi.Umumiy holda, n – oddiy skalyar yoki massiv yoki kiritiladigan ketma – ketlikning uzunligi bo’lishi
mumkin.
( n)
f(A)
- n kattalikdagi ixtiyoriy masalani yechadigan algoritm A bajarish
kerak bo’lgan asosiy amallarni (qo’shish, ayirish, taqqoslash,…) yuqori
chegarasini beradigan ishchi funksiya. Algoritmningsifatini baholash uchun
quyidagi mezonni ishlatamiz.
Agar
( n)
f(A)
o’sish tartibi n dan bog’liq bo’lgan polinomdan katta bo’lmasa, A
algoritm polinomial deb aytiladi, aks holda algoritm A eksponensial hisoblanadi.
Shular bilan birgalikda tahlil jarayonida ko’p matematik fanlarda standart bo’lgan
iboralar ishlatiladi.
Kompyuter fanlari, algoritmlarni tahlil qilish ni topish jarayoni hisoblash murakkabligi algoritmlar - vaqt, saqlash yoki boshqa manbalar miqdori ularni ijro eting. Odatda, bu a ni o'z ichiga oladi funktsiya algoritm kiritish uzunligini va uni bajaradigan qadamlar soniga bog'laydigan (uning vaqtning murakkabligi) yoki u foydalanadigan saqlash joylari soni (uning kosmik murakkablik). Algoritm ushbu funktsiya qiymatlari kichik bo'lganda yoki kirish hajmining o'sishiga nisbatan sekin o'sganda samarali bo'ladi deyiladi. Xuddi shu uzunlikdagi turli xil yozuvlar algoritmning xatti-harakatlariga olib kelishi mumkin, shuning uchun eng yaxshi, eng yomon va o'rtacha ish tavsiflarning barchasi amaliy qiziqish uyg'otishi mumkin. Agar boshqacha ko'rsatilmagan bo'lsa, algoritmning ishlashini tavsiflovchi funktsiya odatda yuqori chegara, algoritmga eng yomon holatlardan aniqlandi.
Algoritmlarni tahlil qilish" atamasi tomonidan kiritilgan Donald Knuth.[1] Algoritmni tahlil qilish keng doiraning muhim qismidir hisoblash murakkabligi nazariyasi, bu berilganni hal qiladigan har qanday algoritm uchun zarur bo'lgan manbalar uchun nazariy baholarni beradi hisoblash muammosi. Ushbu taxminlar izlashning oqilona yo'nalishlari to'g'risida tushuncha beradi samarali algoritmlar.
Algoritmlarni nazariy tahlil qilishda ularning murakkabligini asimptotik ma'noda baholash, ya'ni o'zboshimchalik bilan katta kirish uchun murakkablik funktsiyasini baholash odatiy holdir. Big O notation, Katta-omega yozuvlari va Big-teta yozuvi shu maqsadda ishlatiladi. Masalan; misol uchun, ikkilik qidirish qidirilayotgan tartiblangan ro'yxat uzunligining logarifmiga mutanosib bo'lgan bir necha bosqichda yoki O (log (n)) da, so'zma-so'z " logaritmik vaqt". Odatda asimptotik taxminlar har xil bo'lgani uchun ishlatiladi amalga oshirish bir xil algoritm samaradorligi bilan farq qilishi mumkin. Ammo berilgan algoritmni istalgan ikkita "oqilona" amalga oshirish samaradorligi a deb nomlangan doimiy multiplikativ omil bilan bog'liq. yashirin doimiy.
Ba'zida samaradorlikning aniq (asimptotik bo'lmagan) o'lchovlari hisoblab chiqilishi mumkin, ammo ular odatda algoritmni amalga oshirishda ma'lum taxminlarni talab qiladi, deyiladi hisoblash modeli. Hisoblash modeli an nuqtai nazaridan aniqlanishi mumkin mavhum kompyutermasalan, Turing mashinasi, va / yoki ma'lum bir operatsiyalar birlik vaqtida bajarilishini e'lon qilish orqali, masalan, agar biz ikkilik qidiruv qo'llanadigan tartiblangan ro'yxatda n va biz ro'yxatdagi elementni har bir qidirishni birlik vaqtida, so'ngra eng ko'p jurnalda bajarilishi mumkinligiga kafolat beramiz2 n Javobni qaytarish uchun + 1 marta birlik kerak.
Ikkita algoritm berilgan, qaysi biri yaxshiroq ekanligini qanday aniqlash mumkin?
Eng oddiy yo'li, dasturni ikkita kompyuterda ishga tushirib dasturga turli sonlar kiritish bilan tekshirib ko'rish va qaysi birini kam vaqt olayotganini aniqlash. Ammo, bu usulning juda ko'p kamchiliklari mavjud:
1) Ba'zi sonlar uchun birinchi algoritm, ba'zi sonlar uchun esa ikkinchi algoritm tezroq ishlashi mumkin.
2) Ba'zi sonlar uchun birinchi kompyuterdagi birinchi algoritm, ba'zi sonlar uchun esa ikkinchi algoritm boshqa kompyuterda tezroq ishlashi mumkin.
Algoritmni asimptotik Tahlil qilish yuqoridagi muammolarni bartaraf etishga yordam beradi. Algoritmni asimptotik Tahlil qilishda biz algoritmga turli sonlar kiritilganda u qanday unumdorlik ko'rsatishini baholaymiz. Biz algoritmga kiritilayotgan sonlar ortishi bilan uning ishlash vaqti (yoki xotiradan joy egallashi) qanday ortishini o'lchaymiz (algoritmni ishlash vaqt davomiyligi qanchaligini emas).
Asimptotik Tahlil algoritmni baholash uchun eng yaxshi variantmi?
Asimptotik Tahlil 100% to'g'ri tahlil qilish imkonini bermaydi, ammo algoritmini asimptotik Tahlil qilish mavjud boshqa barcha Tahlil yo'llari ichida eng yaxshisi. Misol uchun, ikkita saralash algoritm bor deb tassavur qilaylik, birinchisiga n son kiritilganda uning ishlash vaqti 100nLog(n) funksiya asosida, ikkinchisiga n son kiritilganda uning ishlash vaqti 2nLog(n) funksiya asosida ortsin. Bu algoritmlarning unumdorligi asimptotik Tahlilda teng deb hisoblanadi (o'sish tartibi nLog(n)), chunki asimptotik Tahlilda konstanta koeffisiyentlar hisobga olinmaydi.
Do'stlaringiz bilan baham: |
