Algoritmlarni baholash mezonlari Reja: I. Kirish Algoritm tushunchasi va uning ta’rifi. II. Asosiy qism Algoritmlarni baholash

Algoritmlarni tahlil qilish; eng yaxshi, eng yomon va o'rtacha ish vaqti.
Bitta masalani echishning turli xil algoritmlarini ko'rib chiqsak, ular qancha hisoblash resurslarini (ishlash vaqti, xotira) talab qilishini tahlil qilish va eng samaralisini tanlash foydalidir. Albatta, hisoblashning qaysi modelidan foydalanilganligi to'g'risida kelishib olishimiz kerak. Ushbu ta'lim, bir model sifatida, eng qismi uchun, biz oddiy bir protsessor foydalanish tasodifiy kirish mashinasi ( tasodifiy - kirish mashinasi , RAM operatsiyalar parallel ijro uchun taqdim emas). Ishlash vaqti ( ish vaqti ) algoritmi ostida biz bajaradigan elementar qadamlar sonini anglatadi. Aytaylik, psevdokodning bir qatorida belgilangan miqdordagi operatsiyalar talab etiladi (agar ba'zi bir xatti-harakatlarning og'zaki tavsifi bo'lmasa - masalan, "hamma nuqtalarni x- koordinata bo'yicha saralash "). Qo'ng'iroq qilish ( qo'ng'iroq qilish ) protsedurasini (ma'lum miqdordagi operatsiyalarni o'z ichiga olgan) va uning bajarilishini ( bajarilishini ) uzoq vaqt davomida ajratib turishingiz kerak .
Algoritmning murakkabligi bu vazifaning o'lchamiga qarab talab qilinadigan manbaning kattaligi tartibini (vaqt yoki qo'shimcha xotira) aks ettiradigan qiymatdir. Shunday qilib, biz algoritmning vaqtinchalik T ( n ) va fazoviy V ( n ) murakkabligini ajratamiz. Murakkablikni baholashni ko'rib chiqishda biz vaqtinchalik murakkablikdan foydalanamiz. Fazoviy murakkablik ham shunga o'xshash tarzda baholanadi. Baholashning eng oson usuli - bu eksperimental, ya'ni algoritmni dasturlash va natijada olingan dasturni bir nechta vazifalar bo'yicha bajarish, dasturlarning bajarilish vaqtini baholash. Biroq, bu usul bir qator kamchiliklarga ega. Birinchidan, eksperimental dasturlash, ehtimol qimmat jarayon. Ikkinchidan, shuni yodda tutish kerakki, dasturlarning bajarilish vaqtiga quyidagi omillar ta'sir qiladi:
1. Dastur algoritmining vaqt murakkabligi;
2. Bajariladigan dasturning kompilyatsiya qilingan kodining sifati;
3. Dasturni bajarish uchun ishlatiladigan mashina ko'rsatmalari.
Ikkinchi va uchinchi omillarning mavjudligi algoritmning vaqt murakkabligi tipik birliklaridan foydalanishga imkon bermaydi (soniya, millisekundlar va boshqalar), chunki agar siz turli xil dasturchilar (algoritmni kim dasturlasa) bir xil algoritm uchun har xil baholarni olish mumkin. o'z), turli xil kompilyatorlar va turli xil kompyuterlar. Ko'pincha, algoritmning vaqt murakkabligi kiritish hajmiga bog'liq. Bu, odatda, bir algoritm vaqti murakkabligi tartibini deb aytiladi T ( n hajmi kirish ma'lumotlari asosida) n . Amaliyotda T ( n ) ning aniq qiymatini aniqlash juda qiyin. Shuning uchun asimptotik munosabatlarga murojaat qiling
O- harflar.
Keyinchalik muhokama qilinadigan algoritmning bajarilish vaqtini nazariy jihatdan hisoblaydigan usul mavjud.

Insertion-Sort protsedurasining umumiy bajarilish vaqtini hisoblash uchun biz uning narxini (operatsiyalar sonini) va ushbu satr har bir satrning yonida necha marta bajarilishini belgilaymiz. 2 dan n gacha bo'lgan har bir j uchun (bu erda n = uzunlik [ A ] - massiv o'lchami), 5 qatori necha marta bajarilishini hisoblash kerak, bu sonni t j bilan belgilaymiz . Davr ichidagi chiziqlar tekshiruvdan bir marta kam bajariladi, chunki oxirgi tekshirish pastadirdan chiqadi. Satr qiymati c takrorlangan t marta hissa beradi c  m operatsiyalar umumiy sonida (ammo, bu ibora ishlatilgan xotira hajmini hisoblash uchun ishlatilishi mumkin emas). Barcha qatorlarning hissalarini qo'shsak, olamiz

Jarayonning ishlash vaqti nafaqat n ga bog'liq , balki kirishning kirish qismida n o'lchamining qaysi qatori bilan ta'minlanganligiga ham bog'liq . Insertion-Sort protsedurasi uchun massiv allaqachon tartiblangan bo'lsa, eng maqbul holat. So'ngra line davr birinchi tekshirish keyin 5 tugaydi (buyon A [ i ] ≤ asosiy uchun i = j - 1), shuning uchun hamma narsani t j umumiy vaqti 1, va

Shunday qilib, eng qulay holatda, vaqt t ( n ), hajmi bir qator saralash uchun zarur n, bir chiziqli funksiya (bo'lgan chiziqli funktsiyasi ) tomonidan n , masalan a va b ba'zi turg'unliklar uchun T ( n ) = a  n + b shakli mavjud . Ushbu Sobit tanlangan qiymatlari orqali aniqlanadi bilan 1 , ... , bilan 8 . Agar qator teskari (pasayish) tartibda joylashgan bo'lsa, ish vaqti protsedura maksimal bo'ladi: A [ j ] har bir elementni A [1] , ..., A [ j - 1] barcha elementlar bilan taqqoslash kerak . Bundan tashqari, t j = j . Chunki

biz eng yomon holatda protsedura vaqti ekanligini tushunamiz.

Bunday holda, T ( n ) - kvadrat ( kvadratik funktsiya ), ya'ni. shakli mavjud T ( n ) = a  n 2 + b  n + s . A , b va c konstantalari bu erda c 1 , ..., c 8 qiymatlari bilan ham belgilanadi .
Bu, odatda, bir algoritm vaqti murakkabligi tartibini deb aytiladi T ( n hajmi kirish ma'lumotlarining) n . Amaliyotda T ( n ) ning aniq qiymatini aniqlash juda qiyin. Shuning uchun, ular yordamida asimptotik munosabatlar murojaat O -symbolics. Masalan, agar algoritm ishlashi uchun talab qilinadigan tadbirlar (harakatlar) soni 16 n 2 + 12 n  log n + 2 n + 3 bilan ifodalangan bo'lsa , u holda algoritm T ( n ) ning O ( n 2 ) tartibida bo'lishini anglatadi. ) Asimptotik Omatikani shakllantirishda , barcha asl ifoda shartlari katta n uchun eng katta hissa qo'shadigan narsa bilan qoldiriladi (qolgan atamalar e'tiborsiz qoldirilishi mumkin) va uning oldidagi koeffitsient e'tiborga olinmaydi (chunki barcha asimptotik baholar doimiygacha berilgan). Belgilangan O () ishlatilganda, ular aniq bajarilish vaqtini anglatmaydi, balki faqat uning yuqori chegarasi, doimiy omilgacha. Masalan, algoritm O ( n 2 ) tartibining vaqtini talab qiladi deb aytganda , ular vazifaning bajarilish vaqti elementlar sonining kvadratidan tezroq o'smasligini anglatadi.
O'rta va eng yomon ish
Algoritmni buyurtma qilishning murakkabligini baholash algoritmlar murakkabligining yuqori chegarasidir. Agar dastur katta murakkablik darajasiga ega bo'lsa, bu algoritm haqiqatan ham uzoq davom etadi degani emas. Ba'zi bir ma'lumot to'plamlarida, algoritmni bajarilishi ularning murakkabligi asosida taxmin qilishdan ancha kam vaqt talab etadi. Masalan, A vektorda berilgan elementni qidiradigan kodni ko'rib chiqing. Agar kerakli element ro'yxatning oxirida bo'lsa, unda dastur N bosqichni bajarishi kerak bo'ladi. Bunday holda, algoritmning murakkabligi O (N) dir. Ushbu eng yomon holatda, algoritmning ishlash vaqti maksimal bo'ladi. Boshqa tomondan, kerakli narsa birinchi holatda ro'yxatda bo'lishi mumkin. Algoritm faqat bitta qadamni bajarishi kerak. Bunday holat eng yaxshi deb nomlanadi va uning murakkabligi O (1) deb baholanishi mumkin.
function Locate(data: integer): integer;
var i:
integer;
fl:
boolean;
begin
fl:=false;
i:=1;
while (not fl) and (i<=N) do
begin
if A[i]=data then
fl:=true else
i:=i+1;
end;
if not fl then
i:=0;
Locate:=I;
end;
Ushbu ikkala holat ham mumkin emas. Bizni kutilgan variant ko'proq qiziqtiradi. Agar ro'yxat elementi dastlab tasodifiy aralashtirilsa, unda kerakli element ro'yxatning istalgan joyida paydo bo'lishi mumkin. O'rtacha, kerakli elementni topish uchun N / 2 taqqoslash talab qilinadi. Shunday qilib, ushbu algoritmning murakkabligi o'rtacha O (N / 2) = O (N).
Bunday holda, o'rtacha va kutilgan murakkablik bir xil, ammo ko'plab algoritmlar uchun eng yomon holat kutilganidan juda farq qiladi. Masalan, eng yomon holatlarda tez tartiblash algoritmi O (N ^ 2) tartibining murakkabligiga ega, kutilayotgan xattiharakatlar esa O (N * log (N)) bahosi bilan tavsiflanadi, bu ancha tezroq