Algoritmlarni loyihalash”

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.

Listing 1.3 - ish vaqtini hisoblash bilan qo'shilgan saralash algoritmining soxta kodi

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 ₁ , ... , bilan ₈ .

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 ² + b  n + s . A , b va c konstantalari bu erda c ₁ , ..., c ₈ 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 ² + 12 n  log n + 2 n + 3 bilan ifodalangan bo'lsa , u holda algoritm T ( n ) ning O ( n ² ) 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 ² ) tartibining vaqtini talab qiladi deb aytganda , ular vazifaning bajarilish vaqti elementlar sonining kvadratidan tezroq o'smasligini anglatadi.

1.2-jadval - funktsiyalarning o'sish sur'atlarini qiyosiy tahlil qilish

1	0	0	1
16	4	64	256
256	8	2 048	65 536
4 096	12	49 152	16 777 216
65 536	16	1 048 565	4 294 967 296
1 048 476	20	20 969 520	1 099 301 922 576

16 775 616

24

402 614 784

281 421 292 179 456

Shakl 1.1 - Turli funktsional bog'liqliklarga misollar

Agar biz 1.2-jadvalda keltirilgan raqamlar mikrosekundlarga to'g'ri keladi deb faraz qilsak, 1048476 elementlar bilan bog'liq muammolar uchun T (log n ) ish vaqti bilan ishlaydigan algoritm 20 mikrosaniyaga kerak bo'ladi va T ( n ² ) ish vaqti algoritmi 12 kundan ko'proq vaqtni oladi.

Agar operatsiya ma'lumotlarning miqdoriga bog'liq bo'lmagan qat'iy miqdordagi qadamlarda bajarilsa, unda O (1) ni yozish odatiy holdir .

Shuni ta'kidlash kerakki, asimptotik baholashda logarifmaning asosi yozilmagan.

Buning sababi juda oddiy. Bor bo'lsin , ey (log ₂ n ). Ammo log ₂ n = log ₃ n / log ₃ 2 va log ₃ 2, har qanday doimiy kabi, O () belgisi hisobga olinmaydi. Shunday

qilib, O (log ₂ n ) = O (log ₃ n ). Xuddi shu tarzda har qanday poydevorga kirish mumkin, bu uni yozishning ma'nosi yo'qligini anglatadi.

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 ₁ ( n ) O ( f ( n )) tartibda
   

bo'lsa , T ₂ ( n ) esa O ( g ( n )) tartibda bo'lsa , u holda T ₁ ( n ) + T ₂ ( 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 holatda 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.