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

for i:=1 to N do
begin
max:=A[i,1];
for j:=1 to N do
begin
if A[i,j]>max then
max:=A[i,j]
end;
writeln(max);
end;
Ushbu algoritmda i o'zgaruvchisi 1 dan N.gacha o'zgaradi, i ning har bir o'zgarishi bilan birga, j o'zgaruvchisi ham 1 dan N ga o'zgaradi. Tashqi aylanishning har bir N takrorlanishida ichki pastadir ham N marta bajariladi. Ichki pastadir takrorlanishlarining umumiy soni N * N dir. Bu O (N ^ 2) algoritmining murakkabligini aniqlaydi. Algoritmning murakkablik tartibini taxmin qilishda faqat eng tez o'sadigan qismdan foydalanish kerak. Vazifalar aylanishi N ^ 3 + N ifodasi bilan tasvirlangan deb taxmin qiling. Bunday holda, uning murakkabligi O ga teng bo'ladi (N ^ 3). Funktsiyaning tez o'sib boruvchi qismini ko'rib chiqish, algoritmning xatti-harakatlarini N.ning ortishi bilan baholashga imkon beradi. Masalan, N = 100 bilan N ^ 3 + N = 1000100 va N = 1000000 o'rtasidagi farq atigi 100 ga teng, bu 0,01%. O ni hisoblashda, ifodalarda doimiy omillarga e'tibor bermaslik mumkin. 3N ^ 3 ish bosqichiga ega bo'lgan algoritm O (N ^ 3) deb hisoblanadi. Bu O (N) nisbati muammoning hajmiga bog'liqligini yanada aniqroq qiladi.
Qiyinchilikni aniqlash
Dasturning eng murakkab qismlari odatda pastadir va qo'ng'iroq qilish protseduralari. Oldingi misolda butun algoritm ikki tsikl yordamida amalga oshirildi. Agar bitta protsedura boshqasini chaqirsa, u holda protseduraning murakkabligini batafsilroq baholash kerak. Agar unda muayyan miqdordagi ko'rsatmalar bajarilgan bo'lsa (masalan, bosib chiqarish), unda bu murakkablikni baholashga deyarli ta'sir qilmaydi. Agar O (N) bosqichlar chaqirilayotgan protsedurada bajarilsa, funktsiya algoritmni sezilarli darajada murakkablashtirishi mumkin. Agar protsedura ko'chadan ichkarisiga chaqirilsa, u holda ta'sir yanada katta bo'lishi mumkin. Misol tariqasida ikkita protsedurani ko'rib chiqing: O (N ^ 3) murakkabligi bilan sekin va O (N ^ 2) murakkabligi bilan.
procedure Slow;
var i,j,k: integer;
begin
for i:=1 to N do
for j:=1 to N do
for k:=1 to N do
какое-то действие}
end;
procedure Fast;
var
i,j: integer;
begin
for i:=1 to N do
for j:=1 to N do
Slow;
end;
procedure Both;
begin
Fast;
end;
Algoritm murakkabligining asosiy ko'rsatkichi muammoni hal qilish uchun zarur bo'lgan vaqt va talab qilinadigan xotira miqdori hisoblanadi. Shuningdek, topshiriqlar sinfi uchun murakkablikni tahlil qilganda ma'lum bir ma'lumotni - kirish hajmini tavsiflovchi ma'lum bir raqam aniqlanadi . Shunday qilib, algoritmning murakkabligi kirish hajmining funktsiyasi degan xulosaga kelishimiz mumkin.
Algoritmning murakkabligi bir xil kirish hajmi bilan farq qilishi mumkin, ammo har xil kirish ma'lumotlari. Eng yomon , o'rta yoki eng yaxshi holatda murakkablik tushunchalari mavjud . Odatda, eng yomon ishning murakkabligi baholanadi. Vaqtning murakkabligi eng yomon holatda, berilgan o'lchamdagi masalani echishda algoritmni bajarish paytida bajariladigan operatsiyalarning maksimal soniga teng bo'lgan kirish hajmining funktsiyasi. Eng yomon holatda, kapasitiv murakkablik bu o'lchamdagi muammolarni echishda foydalanilgan xotira hujayralarining maksimal soniga teng kirish hajmi funktsiyasidir.
Algoritmni o'sish tartibi
Murakkablikning o'sishi tartibi (yoki aksiomatik murakkablik) katta kirish o'lchamiga ega bo'lgan algoritmning murakkablik funktsiyasining taxminiy xatti-harakatlarini tavsiflaydi. Bundan kelib chiqadiki, vaqtning murakkabligini baholashda elementar operatsiyalarni ko'rib chiqishga hojat yo'q, algoritmning bosqichlarini ko'rib chiqish kifoya qiladi.
Algoritmning bosqichi bu ketma-ket joylashgan elementar operatsiyalar to'plami bo'lib, ularning bajarilish vaqti kirish hajmiga bog'liq emas, ya'ni u yuqorida qandaydir doimiy bilan chegaralangan.
Asimptotik baholash turlar
O - eng yomon holat
F (n)> 0 murakkabligini , g (n)> 0 tartibidagi funktsiyani , kirish o'lchamini n> 0 ko'rib chiqing . Agar f (n) = O (g (n)) va o'zgarmas kattaliklar ham bor c> 0 , n 0 > 0 , keyin 0 n 0 .
Bu holda g (n) funktsiya f (n) ning asemptomatik ravishda aniq qiymatidir. Agar f (n) algoritmning murakkabligi funktsiyasi bo'lsa, unda murakkablik tartibi f (n) - O (g (n)) deb belgilanadi.
Bu ibora g (n) dan doimiy omilgacha tez o'smaydigan funktsiyalar sinfini belgilaydi.
Θ - o'rtacha ish uchun ball
Ta'kidlash joizki, n> n 0 uchun f (n) funktsiya hamma joyda c 1 * g (n) va c 2 * g (n) orasida bo'ladi , bu erda c doimiy omil. Masalan, f (n) = n 2 + n bilan ; g (n) = n 2 .
Algoritmni baholash mezonlari
Og'irlikni o'lchashning yagona mezoni (RVC) algoritmning har bir bosqichi vaqtning birligida va xotira xujayrasi bitta hajm birligida (doimiyga aniq) bajarilishini taxmin qiladi.
Logarifmik o'lchov mezoni (LCV) ma'lum bir operatsiya bilan ishlov berilgan operand hajmini va xotira hujayrasida saqlanadigan qiymatni hisobga oladi.
LCV vaqt murakkabligi l (O p ) qiymati bilan belgilanadi , bu erda O p - operandning qiymati.
LCV ning sig'im murakkabligi l (M) qiymati bilan belgilanadi , bu erda M - xotira xujayrasining kattaligi.
Umumiy qiyinchiliklarni baholash xususiyatlari
Endi biz murakkablikni hisoblash uchun eng ko'p ishlatiladigan ba'zi funktsiyalarni sanab o'tamiz. Vazifalar murakkablikning ortib boradigan tartibida keltirilgan. Ushbu ro'yxatdagi funktsiya qanchalik yuqori bo'lsa, bunday taxminga ega algoritm tezroq bajariladi.
1. C doimiy
2. log (log (N))
3. log (N)
4. N ^ C,
8. C ^ N, C> 1
9. N!
Agar murakkablik tenglamasi ushbu funktsiyalarning bir nechtasini o'z ichiga olgan algoritmning murakkabligini baholashni istasak, tenglamani jadvalda joylashgan funktsiyaga kamaytirish mumkin. Masalan, O (log (N) + N!) = O (N!). Agar algoritm kam miqdordagi ma'lumotlarga kamdan-kam hollarda chaqirilsa, O (N ^ 2) murakkabligini maqbul deb hisoblash mumkin, ammo agar algoritm real vaqtda ishlayotgan bo'lsa, O (N) ishlash har doim ham etarli bo'lmaydi. Odatda, N * log (N) murakkablikdagi algoritmlar yaxshi tezlikda ishlaydi. N ^ C murakkablikdagi algoritmlardan faqat S ning kichik qiymatlari uchun foydalanish mumkin, ularning tartibi C ^ N va N funktsiyalari bilan belgilanadigan algoritmlarning hisoblash murakkabligi! juda katta, shuning uchun bunday algoritmlardan faqat oz miqdordagi ma'lumotlarni qayta ishlash uchun foydalanish mumkin.