Prune and search
छंटाई और खोज 1983 में निमरोद मेगिडो द्वारा सुझाए गए अनुकूलन समस्याओं को हल करने की एक विधि है। विधि का मूल विचार एक पुनरावर्ती प्रक्रिया है जिसमें प्रत्येक चरण में इनपुट आकार को एक स्थिर कारक द्वारा कम ("छंटाई") किया जाता है। इस प्रकार, यह कमी और विजय एल्गोरिदम का एक रूप है, जहां प्रत्येक चरण में कमी एक स्थिर कारक द्वारा होती है। आइए इनपुट आकार, पूरे प्रून-एंड-सर्च एल्गोरिदम की समय जटिलता, और प्रूनिंग चरण की समय जटिलता होने दें। फिर निम्नलिखित पुनरावृत्ति संबंध का पालन करता हैः यह द्विआधारी खोज के लिए पुनरावृत्ति जैसा दिखता है लेकिन द्विआधारी खोज के स्थिर पद की तुलना में एक बड़ा शब्द है। प्रून और खोज एल्गोरिदम में एस (एन) आमतौर पर कम से कम रैखिक होता है (क्योंकि पूरे इनपुट को संसाधित किया जाना चाहिए)। इस धारणा के साथ, पुनरावृत्ति का समाधान है। यह या तो विभाजन-और-विजय पुनरावृत्तियों के लिए मास्टर प्रमेय को लागू करके या यह देखकर देखा जा सकता है कि ज्यामितीय श्रृंखला में पुनरावर्ती उप-समस्याओं का समय कम हो जाता है। विशेष रूप से, मेगिडो ने स्वयं अपने रैखिक समय एल्गोरिथ्म में रैखिक प्रोग्रामिंग समस्या के लिए इस दृष्टिकोण का उपयोग किया जब आयाम तय किया जाता है और अंतरिक्ष में बिंदुओं के एक समूह के लिए न्यूनतम घेरने वाले गोले की समस्या के लिए। संदर्भ ज्यामितीय एल्गोरिदम रैखिक प्रोग्रामिंग