Algoritmlar tahlili

ALGORITMLARNING TAHLILI ASOSLARI

Algoritm tahlining asosiy tushunchalari

Boshlang’ich berilganlar sinflari. Algoritmlar boshlang’ich berilganlarning turli guruxlari uchun turlicha murakkablikka ega bo’ladi. Murakkabliklarga qarab boshlang’ich berilganlar bir necha sinflarga bo’linadi. Bitta sinfga tegishli berilganlar uchun algoritm murakkabligi bir xil qiymatga ega.

Xotira bo’yicha murakkablik. Algoritm ish bajarishi uchun qancha xotira sarfi kеrakligini aniqlaydi.

Eng yaxshi holatda algoritm mumkin bo’lgan eng kichik sondagi amallarni bajaradi.

Eng yomon holatda algoritm mumkin bo’lgan eng katta sondagi amallarni bajaradi.

O’rtacha holat murakkabligi formulasi :

Algoritm murakkabligi

n	log2n	n	nlog2n	n2	n3	2n2
1	0.0	1.0	0.0	1.0	1.0	2.0
2	1.0	2.0	2.0	4.0	8.0	4.0
5	2.3	5.0	11.6	25.0	125.0	32.0
10	3.3	10.0	33.2	100.0	1000.0	1024.0
15	3.9	15.0	58.6	225.0	3375.0	32768.0
20	4.3	20.0	86.4	400.0	8000.0	1048576.0
30	4.9	30.0	147.2	900.0	27000.0	1073741824.0
40	5.3	40.0	212.9	1600.0	64000.0	1099511627776.0
50	5.6	50.0	282.2	2500.0	125000.0	1125899906842620.0
60	5.9	60.0	354.4	3600.0	216000.0	1152921504606850000.0
70	6.1	70.0	429.0	4900.0	343000.0	1180591620717410000000.0
80	6.3	80.0	505.8	6400.0	512000.0	1208925819614630000000000.0
90	6.5	90.0	584.3	8100.0	729000.0	1237940039285380000000000000.0
100	6.6	100.0	664.4	10000.0	1000000.0	1267650600228230000000000000000.0

Nazorat savollari:

• Boshlang’ich bеrilganlar sinflari deganda nimani tushunamiz?
• Algoritm tahlining asosiy tushunchalariga nimalar kiradi?
• Xotira bo’yicha murakkablik deganda nimani tushunamiz?
• Eng yaxshi holat uchun murakkablik deganda nimani tushunamiz?
• Eng yomon holat uchun murakkablik deganda nimani tushunamiz?
• O’sish tеzliklari deganda nimani tushunamiz?
• O’sish tеzliklarini tasniflash deganda nimani tushunamiz?