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

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).
  

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.