Министерство по развитию информационных технологий и коммуникаций республики узбекистан каршинский филиал ташкентского университета информационных технологий

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;
Agar Tez protseduraning ichki tsikllarida Slow protsedurasi chaqirilsa, protseduralarning murakkabligi ko'paytiriladi. Bunday holda, algoritmning murakkabligi O (N ^ 2) * O (N ^ 3) = O (N ^ 5) dir. Agar asosiy dastur protseduralarni navbat bilan chaqirsa, unda ularning qiyinchiliklari kuchayadi: O (N ^ 2) + O (N ^ 3) = O (N ^ 3). Quyidagi parcha xuddi shunday murakkablikka ega:
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
{какое-то действие}
end;
procedure Both;
begin
Fast;
Slow;
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 turlari 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. Asimptotik funktsiyalarga misollar

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.
Amalda, algoritmning bajarilish vaqti nafaqat kirish ma'lumotlari miqdoriga, balki ularning qiymatlariga ham bog'liq, masalan, ba'zi saralash algoritmlarining ishlash vaqti sezilarli darajada kamayadi, agar dastlab ma'lumotlar qisman buyurtma qilingan bo'lsa, boshqa usullar bu xususiyatga befarq. Ushbu faktni hisobga olish uchun, ma'lumotlardan mustaqil ravishda algoritmlarni tahlil qilish qobiliyatini saqlab qolish uchun quyidagilar ajralib turadi:
1. maksimal murakkabligi T max ( n ), yoki algoritm eng uzun ishlaydi eng noqulay holatda, murakkabligi;
2. o'rtacha murakkablik T o'rta ( n ) - bu algoritmning o'rtacha murakkabligi;
3. minimal murakkablik T min ( n ) - eng qulay vaziyatda, algoritm eng tez o'tib ketganda murakkablik.
Algoritm vaqt murakkabligini nazariy baholash quyidagi asosiy printsiplar asosida amalga oshiriladi:
1. Topshirish, o'qish, yozish operatsiyalarini bajarish vaqti odatda O (1) tartibida bo'ladi . Istisno bu operandlar massivlar yoki funktsiyalarni chaqirish bo'lgan tayinlash operatorlari;
2. Amallar ketma-ketligini bajarish vaqti ushbu ketma-ketlikdagi eng uzoq bajarilgan vaqtga to'g'ri keladi (yig'ma qoida: agar T 1 ( n ) O ( f ( n )) tartibda bo'lsa , T 2 ( n ) esa O ( g ( n )) tartibda bo'lsa , u holda T 1 ( n ) + T 2 ( n ) tartibli O ( max ( f ( n ), g ( n )));
3. Dallanma konstruktsiyasining bajarilish vaqti (agar-keyin-else) mantiqiy ifodani hisoblash vaqtidan (odatda O (1) tartibida ) va mantiqiy ifoda haqiqiy qiymati bilan va mantiqiy ifodaning noto'g'ri qiymati bilan bajariladigan operatsiyalarni bajarish uchun zarur bo'lgan vaqtning uzunligidan iborat;
4. Tsiklning bajarilish vaqti tsiklning tugatish holatini hisoblash uchun zarur bo'lgan vaqtni (odatda O (1) tartibini ) va tsikl tomonidan bajarilgan takroriy sonlar sonini va tsikl tanasining ishlashi uchun mumkin bo'lgan eng uzoq vaqtni o'z ichiga oladi.
5. Protsedurani chaqirish operatsiyasining bajarilish vaqti chaqirilayotgan protseduraning bajarilish vaqti sifatida belgilanadi;
6. Agar algoritmda shartsiz sakrash operatsiyasi mavjud bo'lsa, unda shartsiz sakrash operatsiyalari yordamida amalga oshiriladigan harakatlar ketma-ketligini hisobga olish kerak.

Shunday qilib, eng yomon holatda va eng yaxshi holatda ish vaqti juda farq qilishi mumkin. Eng tez-tez ishlatiladigan algoritmlarini tahlil yomon holatda operatsiya davomida ( yomon - ishi bilan ishlayotgan vaqtda berilgan kiritish hajmi uchun maksimal muddati sifatida belgilab). Nima uchun? Mana bir necha sabablar.

1. 
   Eng yomon holatda ish vaqtini bilish, algoritmning bajarilishi ma'lum bir vaqtning har qanday kirishida ma'lum vaqt ichida tugashiga kafolat berish mumkin;
   

2. Amalda, "yomon" kirishlar eng ko'p uchraydi (ish vaqti maksimal darajaga yaqin). Masalan, ma'lumotlar bazasi uchun yomon so'rov etishmayotgan narsani qidirish bo'lishi mumkin (juda keng tarqalgan holat);
3. O'rtacha yugurish vaqti eng yomon ishlaydigan vaqtga yaqin bo'lishi mumkin. Masalan, siz n tasodifiy sonlarni ketma -ketligini tartiblashtirish bo'yicha tartiblash yordamida tartiblashtirasiz deylik, 5-8 qatorlarni necha marta aylanib chiqishingiz kerak (Listing 1.3)? O'rtacha, array elementlarini yarim A [1 .. j - 1] dan katta bo'lgan A [ j ] , shunday deb t j o'rtacha teng deb hisoblash mumkin j / 2 , va vaqt t ( n ) quadratically bog'liq n .
Bundan tashqari, ayrim hollarda o'rtacha operatsion vaqt ( vaqt o'rtacha - bir holat da ishlayotgan vaqtda , kutilmoqda ishlayotgan vaqt berilgan uzunligi kirib algoritmi). Albatta, bu qiymat tanlangan ehtimollik taqsimotiga bog'liq va amalda, ma'lumotlarning haqiqiy taqsimlanishi odatda bir xil deb hisoblangan kutilganidan farq qilishi mumkin. Ba'zan tasodifiy sonlar sensori yordamida yagona taqsimotga erishishingiz mumkin.

Foydalanilgan adabiyotlar.
Pro-prof.com
Habr.com
Studfile.net
ziyonet