Algoritmlarni loyihalash”

Asimptotik baholash turlari O - eng yomon holat

F (n)> 0 murakkabligini , g (n)> 0 tartibidagi funktsiyani , kirish o'lchamini n> 0 ko'rib chiqing .

Agar f (n) = O (g (n)) va o'zgarmas kattaliklar ham bor c> 0 , n ₀ > 0 , keyin

0

uchun n> n ₀ .

Bu holda g (n) funktsiya f (n) ning asemptomatik ravishda aniq qiymatidir. Agar f (n) algoritmning murakkabligi funktsiyasi bo'lsa, unda murakkablik tartibi f (n) - O (g (n)) deb belgilanadi.

Bu ibora g (n) dan doimiy omilgacha tez o'smaydigan funktsiyalar sinfini belgilaydi.

Asimptotik funktsiyalarga misollar

f (n)	g (n)
2n ^2 + 7n - 3	n 2
98n * ln (n)	n * ln (n)
5n + 2	n
8	1

Ω - eng yaxshi ball

Ta'rif eng yomon holatlar uchun smeta ta'rifiga o'xshaydi, ammo

f (n) = Ω (g (n)), agar

0

Ω (g (n)) o'sadigan funktsiyalar sinfini aniqlasa. g (n) funktsiyadan doimiy omilgacha sekinroq bo'lmaydi .

Θ - o'rtacha ish uchun ball

Ta'kidlash joizki, n> n ₀ uchun f (n) funktsiya hamma joyda c ₁ * g (n) va c ₂ * g (n) orasida bo'ladi , bu erda c doimiy omil. Masalan, f (n) = n ² + n bilan ; g (n) = n ² .

Algoritmni baholash mezonlari

Og'irlikni o'lchashning yagona mezoni (RVC) algoritmning har bir bosqichi vaqtning birligida va xotira xujayrasi bitta hajm birligida (doimiyga aniq) bajarilishini taxmin qiladi.

Logarifmik o'lchov mezoni (LCV) ma'lum bir operatsiya bilan ishlov berilgan operand hajmini va xotira hujayrasida saqlanadigan qiymatni hisobga oladi.

LCV vaqt murakkabligi l (O _p ) qiymati bilan belgilanadi , bu erda O _p - operandning qiymati.

LCV ning sig'im murakkabligi l (M) qiymati bilan belgilanadi , bu erda M - xotira xujayrasining kattaligi.