1 Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi bo‘yicha qiyinchiliklar

Asimptotiklarning tasodif va farqi
Keling, quyidagi faktga e'tibor qarataylik: f (i) = 0 (? (I)) bahosi f (i) uchun ham yuqori, ham pastki chegaralarni o'rnatadi, chunki uning ta'rifi munosabatning haqiqiyligini taxmin qiladi. c g (n)
Asimptotikaning quyidagi xossasi juda aniq: agar taxmin ph (n) = © ^ (n)) mavjud bo'lsa, tengliklar / ( P) = 0 (^ (i)) va f (i) =? 2 (# (i)), ya'ni. mehnat zichligining yuqori va pastki baholari bir-biriga to'g'ri keladi; agar f (i) = 0 (? max (i)) va ph (n) = C1 ^ mt (n)), va g max (n) fg m Ln (i), keyin hech qanday funktsiya yo'q g (n), shunday qilib / (i) = 0 (? (i)).
Mehnat zichligining yuqori va pastki baholarining mos kelishi quyidagi hollarda mumkin:

• 
  1) kirish uzunligining barcha qiymatlari uchun murakkablik funktsiyasi deterministik (tasodifiy bo'lmagan) funktsiyadir, ya'ni. bajarilgan operatsiyalar soni dastlabki ma'lumotlar qiymatlarining o'ziga xos xususiyatlariga bog'liq emas; bunday, masalan, IZ parchalanish usuli bilan chiziqli algebraik tenglamalar tizimlarini yechish algoritmidagi noma'lum miqdorlar soniga ko'paytirish va bo'lish amallari sonining bog'liqlik funktsiyalari;
  
• 
  2) mehnat intensivligi funktsiyasi tasodifiy funktsiyadir, ya'ni. bajarilgan operatsiyalar soni dastlabki ma'lumotlarning o'ziga xos xususiyatlariga va (yoki) ularni olish tartibiga bog'liq va siz / t | n (i), / max (i) funktsiyalarini belgilashingiz mumkin, minimal va maksimal sonni tavsiflaydi. ma'lum bir kirish uzunligi i uchun algoritm ijrochisi tomonidan bajariladigan amallar, ammo bu funktsiyalarning ikkalasi ham bir xil dominantlarga ega - masalan, ular bir xil tartibdagi ko'phadlardir.
  

Operatsion murakkablik tartibini baholashda uchta muhim qoidani yodda tutish kerak:

• 
  1) murakkablik tartibini aniqlash uchun doimiy omillar muhim emas, ya'ni. 0 (k? g (n)) = 0 (g ("));
  
• 
  2) ikkita funktsiya hosilasining murakkablik tartibi ularning murakkabligi mahsulotiga teng, chunki tenglik to'g'ri:
  
• 
  0 (gl (i) §2(i)) = 0 (? | (i)) 0 (# 2 (i));
  
• 
  3) funksiyalar yig'indisining murakkablik tartibi atamalar dominantining tartibiga teng, masalan: 0 (i e) + n 2 + n) = 0 (i 5).
  

Yuqoridagi qoidalarda faqat bitta asimptotikning belgisi 0 (») ishlatiladi, ammo ular barcha asimptotik baholar uchun amal qiladi - va 0( ) , va &.{ ).
Elementar funktsiyalar to'plamida siz funktsional ustunlik ro'yxatini belgilashingiz mumkin: agar o'zgaruvchi bo'lsa, a, b - sonli konstantalarda quyidagi gaplar to‘g‘ri bo‘ladi: I “Men hukmronman!; Men! hukmronman a "; a" ustunlik qiladi Zj "agar a> b a n hukmronlik qiladi P b agar a har qanday uchun > 1 b e 9? ; n a a / agar hukmronlik qiladi a> b i log q (i) bo'lsa hukmronlik qiladi a > 1.
O'rtacha mehnat intensivligini baholash
Amalda, qayta Ba'zi hisob-kitoblarda M ning murakkabligini matematik kutishning f (n) bahosi katta qiziqish uyg'otadi, chunki aksariyat hollarda f (n) tasodifiy funktsiyadir. Biroq, tasodifiy f (i) bilan algoritmlarni eksperimental o'rganish jarayonida qo'shimcha muammo tug'iladi - M ni ishonchli baholash uchun testlar sonini tanlash. Taklif etilayotgan yechim / (i) ni taxmin qilish uchun beta taqsimotidan foydalanishga asoslangan. Bu juda konstruktiv va ko'p qirrali texnika. Biroq, zamonaviy sharoitda, kompyuterning unumdorligi etarlicha yuqori bo'lsa, ko'p hollarda qiymatlarning joriy o'zgaruvchanligini nazorat qilish asosida testlar hajmini tanlashning oddiyroq usulini qo'llash mumkin. f (n) - qiymatlar baholarning o'zgaruvchanligi belgilangan xatolikdan kam bo'lgunga qadar baholanadi.
Algoritmning operatsion murakkabligini baholash
Algoritmning murakkabligini uning boshqaruv tuzilmalarini tahlil qilish asosida aniqlash mumkin. Loopsiz va rekursiv chaqiruvlarsiz algoritmlar doimiy murakkablikka ega. Shuning uchun algoritmning murakkabligini aniqlash asosan tsikllar va rekursiv chaqiruvlarni tahlil qilishga qisqartiriladi.
O'chirish algoritmini ko'rib chiqing Kimga o'lcham massividan th element P dan harakatlanuvchi massiv elementlaridan iborat (k + 1) dan P-massiv boshiga qaytish va elementlar sonini kamaytirish P birlik uchun. Massivni qayta ishlash siklining murakkabligi Oh (p-k) pastadir tanasi (harakat qilish operatsiyasi) bajarilganligi sababli Kompyuter marta, va pastadir tanasining murakkabligi 0 (1), ya'ni. doimiydir.
Ko'rib chiqilayotgan misolda murakkablik asimptotik 0 (") bilan tavsiflanadi, chunki bu algoritmda bajariladigan operatsiyalar soni ma'lumotlar qiymatlarining o'ziga xos xususiyatlariga bog'liq emas. Murakkablik funktsiyasi deterministik bo'lib, asimptotikaning barcha turlari bir-biriga to'g'ri keladi: f (n) = Q (n-k), f (n) = 0 (n-k) va f (n) = Q (n-dan). Bu fakt © () belgisi bilan tasdiqlanadi. 0 (*) va/yoki 2 (*) dan faqat ushbu asimptotiklar boshqacha bo'lsa foydalanish kerak.
Loop turi (for, while, takrorlash) murakkablikka ta'sir qilmaydi. Agar bir sikl boshqasiga o'rnatilgan bo'lsa va ikkala tsikl ham bir xil o'zgaruvchining o'lchamiga bog'liq bo'lsa, unda butun qurilish kvadratik murakkablik bilan tavsiflanadi. Takroriy uyalar qiyinchilikni oshiradigan asosiy omil hisoblanadi. Misol tariqasida, biz o'lchamdagi massiv uchun taniqli qidirish va saralash algoritmlarining murakkabligini keltiramiz. P:

• 
  ketma-ket qidiruvda taqqoslash operatsiyalari soni: 0 (i);
  
• 
  Ikkilik qidiruvda taqqoslash operatsiyalari soni: 0 (log 2 P);
  
• 
  oddiy almashuv usulida taqqoslash operatsiyalari soni (qabariqli tartiblash): 0 (i 2);
  
• 
  pufakchali tartibdagi almashtirish operatsiyalari soni: 0 (n 2);
  

E'tibor bering, oddiy almashish usulida taqqoslash operatsiyalari soni asimptotikaga ega 0 (n 2) va almashtirish operatsiyalari soni ikki xil asimptotikaga ega 0 (n 2) va? 2 (0), chunki taqqoslashlar soni saralangan ma'lumotlar qiymatlarining o'ziga xos xususiyatlariga bog'liq emas, almashtirishlar soni esa ushbu o'ziga xoslik bilan aniq belgilanadi. O'zgartirishlar umuman amalga oshirilmasligi mumkin - agar ma'lumotlar qatori dastlab to'g'ri tartiblangan bo'lsa yoki almashtirishlar soni maksimal bo'lishi mumkin - taxminan P 2, - agar tartiblangan massiv dastlab teskari yo'nalishda tartiblangan bo'lsa.
Funktsiya nomi g (n) asimptotikada f (n) = @ (t (n)) va f (a) = 0 (g (n)) algoritmni tavsiflash uchun murakkablik funksiyasi / (") ishlatiladi. Shunday qilib, polinom, eksponensial, logarifmik va hokazo murakkablik algoritmlari haqida gapiriladi.