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

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.