|
1.4. Баҳолаш мезонининг хусусиятлари
Алгоритмлар таҳлилида алгоритм бажарган амаллар сонини аниқ билиш катта аҳамият ўйнамайди. Энг муҳими кирувчи маълумотлар ҳажми ортиши билан бу соннинг ўсиш тезлигидир. У алгоритмнинг ўсиш тезлиги дейилади. Агар 1.1- расмга эътибор билан қарасак, у ҳолда функциялар графикларининг қуйидаги хусусиятларини белгилаш мумкин. x2 функция дастлаб секин ўсади, аммо х нинг ўсиши билан унинг тезлиги ҳам ўсади. х ни сақловчи функциялар ўсиш тезлиги ўзгарувчининг барча оралиғида доимий. 2 log x функция умуман ўсмайди, аммо бу кўз алдови. Аслида у ўсади фақат секин.
1.1- расм. Тўртта функция графиклари
Функцияларнинг нисбий баландлиги ўзгарувчининг катта ёки кичик қийматларига боғлиқ бўлади. Функцияларнинг х = 2 даги қийматларини солиштирамиз. Бу нуқтадаги энг кичик қийматли функция х2/8, энг каттаси эса х + 10 функциядир. Аммо х нинг ўсиши билан х2/8 энг катта бўлади ва шундайлигича қолади.
Хулоса қлиб айтганда, алгоритмларнинг таҳлили чоғида бизни алгоритмга тегишли ҳар бир турдаги операциялар сонидан кўра ўсиш тезлиги синфи қизиқтиради. Функциянинг тегишли “ўлчам”и бизни х ўзгарувчининг катта қийматларида қизиқтиради.
Айрим тез учрайдиган функциялар синфлари 1.2-расмдаги жадвалда келтирилган. Бу жадвалда келтирилган синфдан кенг дипозондаги аргумент қийматларидаги функция қийматлари келтирилган. Кўриниб турибдики, катта бўлмаган кирувчи маълумотларда функциялар қийматлари кам фарқланади, аммо ушбу ўлчовларнинг ўсишида фарқ жиддий катталашади. Бу жадвал 1.1 расмдаги таассуротни оширади. Шунинг учун биз каата кирувчи маълумотларда нима содир бўлишини ўрганамиз.
Тез ўсувчи функциялар секинроқ ўсувчи функциялардан устун туради. Шу туфайли агар биз алгоритм мураккаблиги икки ёки ундан ортиқ шундай функциялар йиғиндисини ифодалашини аниқласак, у ҳолда бошқаларидан кўра тезроқ ўсувчи функциялардан бошқа барчасини ташлаб юборамиз. Масалан, агар биз алгоритм таҳлилида у солиштириш бажаришини аниқласак, у ҳолда биз алгоритм мураккаблиги ҳудди дек ўсади деймиз. Бунинг сабаби шуки, 100 кирувчи маълумотларда ва орасидаги фарқ 0.3% ни ташкил этади.
n
|
log2n
|
n
|
n log2n
|
n2
|
n3
|
2 n
|
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
|
|
1.2-расм. Функциялар ўсиш синфлари
1.4.1. Баҳолаш мезонини усуллари
Алгоритм мураккаблиги ўсиш тезлиги муҳим аҳамият касб этади ва биз кўрдикки, ўсиш тезлиги формуланинг юқори устун қисми билан аниқланади. Шунинг учун секин ўсувчи кичик қисмларни қисқартирамиз. Барча кичик қисмларни ташлаб юбориб функциянинг ёки алгоритмнинг тартиби деб номланувчи мураккаблик ўсиш тезлигига эга бўламиз. Алгоритмларни мураккаблигини уларнинг ўсиш тезликлари бўйича гуруҳлаштириш мумкин. биз уч категорияни киритамиз: мураккаблиги ҳеч бўлмаганда ушбу фунция тезлигидек ўсадиган алгоритмлар, мураккаблиги ҳудди шундай тезликда ўсадиган алгоритмлар ва мураккаблиги ушбу функциядан секин ўсадиган алгоритмлар.
Катта Омега
Ҳеч бўлмаганда f функция тезлигида ўсувчи функциялар синфини билан белгилаймиз (катта омега деб ўқилади). д функция ушбу синфга тегишли, агар n аргументнинг барча қийматларида қандайдир мусбат с сони учун тенгсизлик бажарилса. синф ўзининг пастки чегарасини беради, яъни ундаги барча функциялар ҳеч бўлмаганда f дек тез ўсади.
Биз алгоритмларнин самарадорилги билан шуғулланамиз, шунинг учун синф бизни унчалик қизиқтирмайди. Масалан, га n2дан кўра тез ўсувчи функциялар (n3 ва 2n) киради.
Катта О
(катта о деб ўқилади) билан f дан тез ўсмайдиган функциялар синфини белгилаймиз. f функция синфнинг юқори чегарасини билдиради. Расмий нуқтаи назардан д функция синфга тегишли, агар n аргументнинг барча қийматларида қандайдир мусбат с сони учун тенгсизлик бажарилса.
Ушбу синф биз учун жуда муҳим. Икки алгоритмдан бизни улардан бирининг иккинчисига кўра мураккаблиги катта о га тегишлилиги қизиқтиради. Агар шундай бўлса, у ҳолда, демак, иккинчи алгоритм биринчига қараганда масалани яхши ечмайди.
Катта Тета
билан (катта тетеа деб ўқилади) билан f дек тез ўсадиган функциялар синфини белгилаймиз. Расмий нуқтаи назардан ушбу синф юқоридаги икки синфнинг кесишмасини билдиради,
Алгоритмларни солиштиришда бизни ўрганилган алгоритмлардан кўра масалани тез ечувчилари қизиқтиради. Шу туфайли топилган алгоритм ушбу синфга тегишли бўлса у биз учун унча қизиқарли эмас, биз бу синфга тез мурожаат қилмаймиз.
Do'stlaringiz bilan baham: |
