विभाजित आणि जिंकणे समस्या सोडवते (1) त्याला विभाजित करून लहान उप-समस्यांमध्ये, (2) प्रत्येकाला जिंकून पुनरावर्तीपणे, आणि (3) परिणाम एकत्रित करून. अनेक कार्यक्षम अल्गोरिदम या टेम्पलेटचे अनुसरण करतात.
जर उप-समस्या स्वतंत्र असतील आणि द्रुतपणे कमी होत असतील, तर एकूण कार्य एक पुनरावृत्तीचे अनुसरण करते जे तुम्ही मास्टर प्रमेय सह विश्लेषण करू शकता.
def max_dc(arr, lo, hi):
if lo == hi: # base case: one element
return arr[lo]
mid = (lo + hi) // 2
left = max_dc(arr, lo, mid) # conquer left
right = max_dc(arr, mid + 1, hi) # conquer right
return max(left, right) # combine
max_dc([3, 9, 2, 7], 0, 3) # -> 9
अनेकदा T(n) = a·T(n/b) + f(n); मर्ज सॉर्टसाठी, T(n) = 2T(n/2) + O(n) = O(n log n).
जेव्हा समस्या स्वच्छपणे विभाजित होत असेल स्वतंत्र उप-समस्यांमध्ये तेव्हा वापरा. जर उप-समस्या ओव्हरलॅप असतील, तर गतिशील प्रोग्रामिंग (पुनर्गणना टाळण्यासाठी) सुलभ करा. पुनरावर्तन ओव्हरहेड आणि एकत्रीकरण पद्धती लहान इनपुटसाठी प्रभावी असू शकतात.
विभाजित-आणि-जिंकणे हा पुनः वापरणीय खाका आहे जो कार्यक्षम अल्गोरिदमच्या मोठ्या अंशाच्या मागे असतो.
पद्धती ओळखल्याने तुम्ही पुनरावृत्तींसह द्रुतपणे नवीन अल्गोरिदम तयार आणि विश्लेषण करू शकता.
हे समांतर प्रक्रियेवर नैसर्गिकरित्या मॅप होते, कारण स्वतंत्र उप-समस्या एकाचवेळी चालू शकतात.
सविस्तर उत्तरांसह IT मुलाखत प्रश्नांचे ग्रंथालय — Junior पासून Senior पर्यंत.
देणगी द्या