«amaliy matematika va informatika» kafedrasi «Algoritmlar nazariyasi» fanidan Mustaqil ish

Asimptotik taxmin turlari

O - bu eng yomon taxmin

Murakkablikni koʻrib chiqing f (n)\u003e 0, xuddi shu tartibdagi funktsiya g (n)\u003e 0, kirish kattaligi n\u003e 0.
Agar a f (n) \u003d O (g (n)) va doimiylar mavjud c\u003e 0, n 0\u003e 0keyin
0 < f(n) < c*g(n),
uchun n\u003e n 0.

Bu holda g (n) funktsiyasi f (n) uchun asimptotik keskin baho hisoblanadi. Agar f (n) algoritmning murakkabligi funktsiyasi boʻlsa, unda murakkablik tartibi f (n) - O (g (n)) deb belgilanadi.

Ushbu ibora doimiy koeffitsientgacha g (n) dan 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 taxminiy taxmin

Biroq, taʻrif eng yomon taxminlarga oʻxshaydi
f (n) \u003d Ω (g (n)), agar a
0

< c*g(n) < f(n)

Ω (g (n)) funktsiyadan sekinroq oʻsmaydigan funktsiyalar sinfini belgilaydi g (n) doimiy omilgacha.

Θ - oʻrtacha ish uchun taxmin

Shuni aytib oʻtish joizki, bu holda funktsiya f (n) da n\u003e n 0 oʻrtasida hamma joyda mavjud c 1 * g (n) va c 2 * g (n), bu erda c doimiy omil.
Masalan, uchun f (n) \u003d n 2 + n; g (n) \u003d n

Algoritmlarning murakkabligini baholash mezonlari

Yagona vazn mezonlari (MWC) algoritmning har bir bosqichi bir vaqtning birligida, xotira katakchasining bir birlik birligida (doimiyga aniq) bajarilishini nazarda tutadi.
Logaritmik vazn sinovi (LWC) maʻlum bir operatsiya bilan qayta ishlanadigan operand hajmini va xotira joyida saqlanadigan qiymatni hisobga oladi.


DLC-ning vaqt murakkabligi qiymati bilan belgilanadi l (O p)qayerda O p Operandning qiymati.
LECda sigʻimning murakkabligi qiymati bilan belgilanadi l (M)qayerda M - xotira katakchasining kattaligi.