1-laboratoriya ishi. Algoritmni asosiy ta`riflari, xossalari va ularning turlari. Hisoblash modellari va algoritmlarning murakkabligi. Murakkablikning asosiy resurslari: vaqt, xotira. Oddiy klassik algoritmlarni murakkabligi baholash

Eng yaxshi natijalar uchun -baholash

Ta'rif eng yomon holatlarni baholashning ta'rifiga o'xshaydi:

agar



Ω (g(n)) g(n) funksiyadan doimiy koeffitsiyentgacha sekin o'smaydigan funksiyalar sinfini belgilaydi.

Θ - o'rtacha holat uchun baholash

Shuni aytib o'tish joizki, bu holda funksiyasi uchun va orasida hamma joyda bo'ladi, bu yerda c konstanta hisoblanadi.

Masalan, bo'lganda; .

Algoritm murakkabligini baholash kriteriyalari

Bir xil me’yorda o’lchash kriteriyasi algoritmning har bir bosqichi bir vaqt birligida, xotira yacheykasi esa hajmning bir birligida (konstanta bo’yicha aniqlikda) bajarilishini nazarda tutadi.

Logarifmik o’lchash kriteriyasi ma'lum amal bilan qayta ishlanadigan operand o’lchamini va xotira yacheykasida saqlanadigan qiymatni hisobga oladi.


1-misol. Faktorialni hisoblashning murakkabligini baholash.
#include

using namespace std;

int main()

{

int n = 20;

long long result=1;

for (int i=2; i<=n; i++)

result *=i;

cout<

return 0;

}
Berilgan masalaning kirish kattaligi n ekanligini aniqlash oson.

Qadamlar soni (n - 1).

Shunday qilib, bir xil me’yorda o’lchash kriteriyasi uchun vaqt murakkabligi O(n) dir.