Prune and search
કાપણી અને શોધ એ 1983માં નિમરોદ મેગિડો દ્વારા સૂચવવામાં આવેલી ઓપ્ટિમાઇઝેશન સમસ્યાઓને ઉકેલવાની એક પદ્ધતિ છે. પદ્ધતિનો મૂળભૂત વિચાર એક પુનરાવર્તિત પ્રક્રિયા છે જેમાં દરેક તબક્કે ઇનપુટનું કદ સતત પરિબળ દ્વારા ઘટાડવામાં આવે છે ("કાપવામાં આવે છે"). જેમ કે, તે ઘટાડો અને વિજય અલ્ગોરિધમનો એક પ્રકાર છે, જ્યાં દરેક તબક્કે ઘટાડો એક સ્થિર પરિબળ દ્વારા થાય છે. ચાલો ઇનપુટ કદ હોઈએ, સમગ્ર કાપણી અને શોધ અલ્ગોરિધમનો સમય જટિલતા હોઈ શકે, અને કાપણી પગલાની સમય જટિલતા હોઈ શકે. પછી નીચેના પુનરાવર્તન સંબંધનું પાલન કરે છેઃ આ દ્વિસંગી શોધ માટે પુનરાવર્તન જેવું લાગે છે પરંતુ દ્વિસંગી શોધના સતત શબ્દ કરતાં મોટો શબ્દ ધરાવે છે. પ્રૂન અને સર્ચ અલ્ગોરિધમ્સમાં S (n) સામાન્ય રીતે ઓછામાં ઓછું રેખીય હોય છે (કારણ કે સમગ્ર ઇનપુટ પર પ્રક્રિયા થવી આવશ્યક છે). આ ધારણા સાથે, પુનરાવર્તનનો ઉકેલ છે. આ ક્યાં તો વિભાજન-અને-વિજય પુનરાવર્તનો માટે મુખ્ય પ્રમેય લાગુ કરીને અથવા ભૌમિતિક શ્રેણીમાં પુનરાવર્તિત પેટા સમસ્યાઓ માટેનો સમય ઘટે છે તેનું નિરીક્ષણ કરીને જોઈ શકાય છે. ખાસ કરીને, મેગિડોએ પોતે આ અભિગમનો ઉપયોગ તેના રેખીય સમય અલ્ગોરિધમમાં રેખીય પ્રોગ્રામિંગ સમસ્યા માટે જ્યારે પરિમાણ નિશ્ચિત હોય અને અવકાશમાં બિંદુઓના સમૂહ માટે ન્યૂનતમ ઘેરાયેલા ગોળાની સમસ્યા માટે કર્યો હતો. સંદર્ભો ભૌમિતિક અલ્ગોરિધમ્સ રેખીય પ્રોગ્રામિંગ