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

Vaqtinchalik murakkablik - uzunlikdagi kirish ma'lumotlari bo'yicha algoritmning ishlash vaqtining asimptotik bahosi P. Shubhasiz, hisoblash protseduralarini parallellashtirish mavjud bo'lmaganda, algoritmning ishlash vaqti bajarilgan operatsiyalar soni bilan yagona aniqlanadi. Operatsiyalarning davomiyligini ifodalovchi doimiy koeffitsientlar vaqt murakkabligi tartibiga ta'sir qilmaydi, shuning uchun operatsion va vaqt murakkabligi uchun formulalar ko'pincha bir-biriga to'g'ri keladi.
Kapasitiv murakkablik - uzunlikdagi kirish ma'lumotlari bo'yicha algoritmni bajarishda bir vaqtning o'zida mavjud bo'lgan skalerlar sonining asimptotik bahosi P.
Strukturaviy murakkablik - algoritmdagi boshqaruv tuzilmalari sonining xarakteristikasi va ularning interpozitsiyasining o'ziga xosligi.
Kognitiv murakkablik - amaliy sohalardagi mutaxassislar tomonidan tushunish uchun algoritm mavjudligining xarakteristikasi.
Asimptotiklarning turlari va belgilanishi
Algoritmlarning asimptotik tahlilida matematik asimptotik tahlilning yozuvidan foydalanish odatiy holdir. Bunday holda, algoritmlarning murakkabligining uchta bahosi (asimptotikasi) ko'rib chiqiladi, ular quyidagicha belgilanadi:

• 
  1) / (i) = O ^ (n))- murakkablik funksiyasining asimptotik aniq bahosi / («), yoki algoritmning operatsion murakkabligi;
  
• 
  2) /(n) = 0 (§ (n)) - murakkablik funktsiyasi uchun asimptotik keskin yuqori chegara / ( P);
  
• 
  3) / (n) =? 2 (# (n)) murakkablik funksiyasi uchun asimptotik aniq past bahodir / ( P).
  

Belgilash o'rniga C1 ^ (n)) juda tez-tez "o" harfi bilan oddiyroq o (^ (")) kichik kursivda ishlatiladi.
Formulalarning semantikasini misol orqali tushuntirib beraylik: agar u / (i) = 0 (^ 2 (l)) deb yozilsa, BU funksiyani bildiradi. g (n) = og2 (n) murakkablik funksiyasi uchun asimptotik aniq bahodir / (a). Aslida, bayonot shaklida ikki pozitsiyali ta'rif mavjud:
Agar f (n)= @ (jurnal 2 (")),
mo g (n)= log 2 (l) - f (n) uchun asimptotik keskin taxmin.
E'tibor bering, doimiy omil algoritmning murakkablik tartibiga ta'sir qilmaydi, shuning uchun logarifmik murakkablikni ko'rsatishda logarifm asosi o'tkazib yuboriladi va ular shunchaki / (n) = @ (log (n)) ni yozib, shuni nazarda tutadi. logarifm birdan katta ixtiyoriy asosga ega.
Asimptotiklarning rasmiy ta'riflari
Mehnat intensivligi funksiyasining asimptotik keskin bahosi Bilan, Bilan 2, n 0 shunday bo'lsinki, n> n 0 uchun f (n) funksiyasi o'zgarmas koeffitsientlargacha funksiyadan farq qilmaydi. g ( l), keyin funksiya g (n) f (x) funktsiyasi uchun asimptotik o'tkir taxmin deyiladi.

• 
  3 s], s 2 e F, x bilan > 0, 2> bilan 0:
  
  • 
    (3 l 0 e K, l 0> 0: (/ l e K, l> l 0: 0 g (n) / (l) = 0 (? (L)),
    

bu yerda 9 ^, N mos ravishda barcha haqiqiy va natural sonlar to‘plamidir.
Murakkablik funksiyasi uchun asimptotik keskin yuqori chegara og'zaki ravishda quyidagicha aniqlanadi: agar ijobiy raqamlar bo'lsa Bilan va n 0 shunday bo'lsinki, n> n 0 uchun f (n) funksiya funktsiyadan tezroq o'smaydi. g (n) doimiy koeffitsient c gacha, keyin funksiya g (n) funksiya uchun asimptotik keskin yuqori chegara deyiladi Ap).
Ta'rifning aniqroq rasmiy belgisi quyidagicha:

• 
  3 Bilan e % s> 0:
  
  • 
    (3 l 0 e X, l 0> 0: (/ l e K, l> l 0: 0 s? # (L))) 0 (g (n))
    

Murakkablik funktsiyasi uchun asimptotik keskin pastki chegara og'zaki ravishda quyidagicha aniqlanadi: agar ijobiy raqamlar bo'lsa Bilan va n 0 shunday bo'lsinki, n> n 0 uchun f (n) funksiya funksiyadan sekin o'smaydi. g (n) doimiy omilgacha Bilan, u holda funksiya?(l) funksiya uchun asimptotik keskin pastki chegara deyiladi
Ta'rifning aniqroq rasmiy belgisi quyidagicha:

• 
  3 Bilan e 9 ^, Bilan > 0:
  
  • 
    (3 i 0 e X, i 0> 0: (/ i e K, i > men 0: 0 s? g (n)
    

/(men) = 0. ^ (N))
Quyidagilarga e'tibor bering:

• 
  1) asimptotikaning rasmiy ta'riflarida ko'rsatilgan tengsizliklar, umumiy holda, bir emas, balki ba'zi funktsiyalar to'plamini, ko'pincha cheksiz atamalar to'plamini qondirishi mumkin, shuning uchun konstruktsiyalar Q (g (n)), 0 ^ (n)) va 0. ^ (N)) ramziy qiladi ko'p funktsiyalar u bilan mehnat intensivligining tekshirilgan funktsiyasi f (i) solishtiriladi; shundan kelib chiqqan holda, f (x) = 0 (q (x)), f (f0 = 0 (q max (n)), d) = q 2 (q mn (x)) ko'rinishdagi asimptotikaning yozuvida. ) "=" belgisi o'rniga "e" belgisidan foydalanish oqilonaroq bo'ladi;
  
• 
  2) konstruksiyalar (d ^ (n)), 0 ^ (n)) va ? 1 ^ (n)), Ba'zi miqdorlar uchun belgi sifatida qo'llaniladigan so'zlar mos ravishda quyidagicha o'qilishi kerak: mos keladigan har qanday funktsiya tezroq o'smaydi va sekinroq o'smaydi. g (n).