Мундарижа Кириш

Катта О синфининг тафсилоти
Берилган функцияни синфга тегишлилигини икки усул билан текшириш мумкин: ё юқорида аниқланган усул билан ёки қуйидагича:
, если қандайдир ўзгармас с учун. (1.23)
Бу шуни билдирадики, агар муносабат мавжуд ва у чексизликдан кичик бўлса, у ҳолда . Айрим функциялар учун бу оддий текшириш эмас. Лопитал қоидасига кўра, бундай ҳолда функцияларни уларнинг кўпайтмалари билан алмаштириш мумкин.
Белгилашлар
, ва синфларнинг ҳар бири тўплам ҳисобланади, шунинг учун “д – ушбу тўплам элементи” ифодаси ўринли. Таҳлилда баъзида ёзамиз, аслида эса ни билдиради.
1.5. «Бўлаклаш ва бошқариш» шаклидаги алгоритмлар
Юқорида таъкидлаганимиздек, «бўлаклаш ва бошқариш» шаклидаги алгоритмлар турли масалаларни ечишда ихчам ва кучли восита бўлиб ҳисобланади. Уш бу бўлимда биз нафақат бундай алгоритмларни тузиш билан, балки уларнинг таҳлили билан ҳам шуғулланамиз. Циклдаги солиштиришларни ҳисоблашда бизга циклнинг бир итерациясидаги солиштиришларни ҳисоблаш кифоя ва уларни итерациялар сонига кўпайтирамиз. Ушбу ҳисоб агар ички цикл итерациялари сони ташқи цикл параметрларига боғлиқ бўлса мураккаблашади.
«Бўлаклаш ва бошқариш» шаклидаги алгоритмлардаги итерацияларни ҳисоблаш осон эмас, яъни у бошланғич ва якунловчи ҳаракатлардан, рекурсив чақурувлардан боғлиқ. Одатда рекурсив чақирувларда у ёки бу функция неча марта бажарилиши ноаниқ бўлади. Мисол сифатида қуйидаги алгоритмни қараймиз.
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 деб номланган) алгоритм ёрдамида ечиш мумкин бўлган ҳолни текширади, агар шундай бўлса у ҳолда у чақирилади. Агар масала жуда катта бўлса, у ҳолда дастлаб кирувчи маълумотларни бир қанча (уларнинг сони numberSmaller га тенг) кичик тўпламларга ажратувчи Dividelnput процедураси чақирилади. Бу кичик тўпламларнинг барча бир хил ўлчамли ёки жиддий фарқ қилиши мумкин. бошланғич кирувчи тўпламдаги ҳар қайси элемент ҳеч бўлмаганда кичик тўпламлардан бирига тушади, аммо бир элемент бир қанча тўпламларга тушиши ҳам мумкин. Кейин ҳар бир кичик тўпламларда DivideAndConquer алгоритм рекурсив чақирилади, CombineSolutions функция эса олинган натижаларни бир натижага олиб келади.
Натурал соннинг факториалини циклда ҳисоблаш қийин эмас, аммо қуйидаги мисолда бизга бу ҳисоблашнинг рекурсив варианти зарур бўлади. N сонининг факториали N нинг N – 1 сон факториалига кўпайтмасига тенг. Шу сабабли кейинги алгоритм қўл келади:
Factorial(N)
N сон,бизга керак бўлган факториал
Factorial бутун сонга эга бўлади


if (N=1) then
return 1
else
smaller = N-1
answer=Factorial(smaller)
return (N*answer)
end if
Ушбу алгоритмнинг қадамлари оддий ва тушунарли ва биз уни юқоридаги стандарт алгоритм билан солиштиришимиз мумкин. Юқорида таъкидлаганимиздек кўпайтириш амали қўшиш амалига қараганда мураккаброқ, шунинг учун кўпайтиришни алоҳида ҳисоблаш керак. Мисолни соддалаштириш учун бу фарқни ҳисобга олмаймиз.
Ушбу икки алгоритмларни таққослашда кўриниб турибдики бизнинг ҳолда маълумотларнинг сўнгги ўлчами 1 ва бундай маълумотларда ҳеч қандай арифметик амаллар бажарилмайди. Қолган барча ҳолларда else қисмга келамиз. Умумий алгоритмнинг биринчи қадамида «киришларни кичик қисмларга ажратиш» бажарилади; факториални ҳисоблаш алгоритмида эса бу қадамга битта айиришни талаб қилувчи ўзгарувчи smaller ни ҳисоблаш мос келади. Умумий алгоритмнинг кейинги қадами кичик маълумотларни қайта ишловчи процедурани рекурсив чақириш ташкил этади; факториални ҳисоблаш алгоритмида бу битта рекурсив чақирув ва масала ўлчами аввалгисидан 1 га кам. Умумий алгоритмнинг охирги қадами ечимларни бирлаштириш бўлса, факториални ҳисоблаш алгоритмида бу охирги return операторидаги кўпайтиришдир.