Рекурсив бўлмаган алгоритмларнинг математик таҳлили - Ушбу бўлимда биз рекурсив бўлмаган алгоритмларнинг вақт самарадорлигини таҳлил қилиш учун одинги бўлимда кўрсатилган умумий асосни мунтазам равишда қўллаймиз. Келинг, бундай алгоритмларни таҳлил қилишда одатда қўлланиладиган барча асосий қадамларни кўрсатадиган жуда оддий мисолдан бошлайлик.
- Масалан: n та сондан иборат рўйхатдаги энг катта элементнинг қийматини топиш масаласини кўриб чиқайлик. Оддийлик учун биз рўйхат массив сифатида амалга оширилган деб тахмин қиламиз. Қуйида муаммони ҳал қилиш учун стандарт алгоритмнинг коди келтирилган.
Бу эрда кириш ўлчамининг табиий ўлчови, n массивдаги элементлар сони.
Энг ички ҳалқа битта операцияни (икки элементни таққослаш) ўз ичига олганлиги сабабли, биз буни алгоритмнинг асосий операцияси деб ҳисоблашимиз керак.
Таърифга кўра, энг ёмон ҳолат киритиш - бу массив бўлиб, у учун элементларни таққослаш сони Cworst(n) n ўлчамдаги барча массивлар ичида энг каттаси бўлади.
Рекурсив алгоритмларнинг математик таҳлили - Ушбу бўлимда биз алгоритмларни таҳлил қилиш учун умумий асосни рекурсив алгоритмларга қандай қўллашни кўриб чиқамиз. Биз кўпинча рекурсив алгоритм ғоясига янгиликлар киритиш учун ишлатиладиган мисолдан бошлаймиз.
- Масалан: Ихтиёрий манфий бўлмаган н бутун сони учун F(n) = n! факториал функциясини ҳисобланг.
- F(n) = F(n− 1) ни ҳисоблашимиз мумкин. н қуйидаги рекурсив алгоритм билан.
Do'stlaringiz bilan baham: |
