|
Катта О синфининг тавсифи
Берилган функция O(f) га тегишли эканлигини икки хил йўл билан текшириш мумкин: юқоридаги тавсиф орқали ёки қуйидаги тавсиф ёрдамида:
= с ихтиёрий с константа учун. (1.23)
Бу шуни англатадики, g(п)/f(n) нинг муносабатлар чегараси мавжуд бўлса ва у чексизликдан кичик бўлса, g€O (f) бўлади. Баъзи функциялар учун буни текшириш осон эмас. Лопиталь қонунига кўра, бундай ҳолда функциялар чегарасини уларнинг ҳосиласи чегарасида алмаштириш мумкин.
Белгилаш
Θ(f),Ω(f), ва О(f) синфларининг ҳар бири тўплам ҳисобланади, шунинг учун «g – шу тўплам элементи» ибораси аҳамиятлидир. Бироқ, таҳлилларда g = O(f)деб ёзишади, аслида эса g€O (f).
«Тақсимла ва бошқар» кўринишидаги алгоритмлар
Кириш қисмида айтиб ўтилганидек, «тақсимла ва бошқар» кўринишидаги алгоритмлар турли масалаларни ечиш учун ихчам ва кучли қуролни таъминлайди. Бу бўлимда биз бундай алгоритмларни ишлаб чиқиш эмас, балки уларнинг таҳлили билан шуғулланамиз. Циклларда таққослашлар сонини ҳисоблашда циклнинг бир итерациясидаги таққослашлар сонини ҳисоблаб, уни итерациялар сонига кўпайтириш етарли. Агар ички циклнинг итерациялар сони ташқи параметрларга боғлиқ бўлса, ҳисоблаш қийинроқ бўлади. «Тақсимла ва бошқар» кўринишидаги алгоритмлар итерациясини ҳисоблаш оддий эмас: у рекурсив чақириқлар, тайёрлов ва якунланувчи ҳаракатларга боғлиқ. рекурсив чақирувда у ёки бу функциянинг неча марта бажарилиши, одатда, аниқ эмас. Мисол сифатида қуйидаги «тақсимла ва бошқар» кўринишидаги алгоритмни кўриб чиқамиз:
DivideAndConquer (data, N, solution)
data //кирувчи маълумотлар тўплами
N //тўпламдаги қийматлар сони
solution //масала ечими
if (N <= SizeLimit) then
DirectSolution(data,N,solution) else
DivideInput(data,N,smallerSets,smallerSizes,numberSmaller) for i=l to numberSmaller do
DivideAndConquer(smallerSets[i],smallerSizes[i],smallSol[i]) end for
CombineSolutions(smallSol.numberSmaller,solution)
end if
Бу алгоритм ечимини оддий рекурсив бўлмаган алгоритм (матнда DirectSolution деб аталувчи) ёрдамида топиш учун вазифанинг ҳажми кичик эмаслигини аввал текширади ва агар шундай бўлса, унинг чақириғи содир бўлади. Агар вазифа жуда ката бўлса, аввал Divide Input амали чақирилади, у кирувчи рақамларни бир қанча кичик тўпламларга бўлади (уларнинг сони numberSmaller га тенг). Кирувчи дастлабки тўпламнинг ҳар бир қисми кичикроқ тўпламлардан бирига тушади, аммо бир элементнинг ўзи бир нечта тўпламга тушиши мумкин. Сўнг ҳар бир кичик кирувчи тўпламда DivideAndConquer алгоритмининг рекурсив чақируви содир бўлади, CombineSolutions функцияси олинган натижаларни бирлаштиради.
Натурал соннинг факториалини циклда ҳисоблаш қийин эмас, бироқ қуйида берилган мисолда бизга ушбу ҳисоблашнинг рекурсив варианти керак бўлади. JV сонининг факториали N ни, N — 1 сонининг факториалига кўпайтирилганига тенг. Шунинг учун қуйидаги алгоритм керак бўлади:
Factorial(N)
N // число, факториал которого нам нужен
Factorial // возвращает целое число
if (N=l) then
return 1 else
smaller = N-l
answer=Factorial(smaller)
return (N*answer) end if
Бу алгоритмнинг қадамлари оддий ва тушунарли ва биз уларни юқорида келтирилган стандарт алгоритм Билан солиштиришимиз мумкин. Биз аввалроқ бу бўлимда кўпайтириш амали қўшишдан мураккаброқ, деб эслатган бўлсакда, кўпайтиришни алоҳида ҳисоблаш керак. Мисолни соддалаштириш учун биз бу чегарани ҳисобга олмаймиз.
Бу икки алгоритмни таққосласак, рақамлар ўлчамининг чегараси 1 эканлиги кўринади ва бунда ҳеч қандай арифметик амал бажарилмайди. Бошқа барча ҳолларда биз else даражасига ўтамиз. Умумий алгоритмдаги биринчи қадам «киришнинг кичик қисмларга бўлиниши» бўлади; ҳисоблаш алгоритмида бу қадамнинг факториалига битта айиришни талаб қилувчи smaller ўзгарувчисини ҳисоблаш тўғри келади. Умумий ва бошқар алгоритмининг кейинги қадами кичикроқ рақамларни қайта ишлаш амалини рекурсив чақириш ҳисобланади; факториални ҳисоблаш алгоритмида – бу бир рекурсив чақириқ ва ундагивазифанинг ҳажми аввалгидан битта кам.
Умумий алгоритмдаги охирги қадам тенгламаларни бирлаштиришдан иборат; факториални ҳисоблаш алгоритмида бу кўпайтириш охирги return операторида бажарилади.
Do'stlaringiz bilan baham: |
