हो सकता है कि एक अच्छी शुरुआत इस समस्या के लिए आवर्ती संबंध को देखने के लिए। मैं ठेठ mergesort के लिए कल्पना यह कुछ इस तरह दिखेगा:
T(N) = 2 * T(N/2) + N
यानी आप आधे आकार के 2 subproblems में समस्या विभाजित कर रहे हैं, और उसके बाद एन काम (मर्ज) का प्रदर्शन किया। हमारे पास एक आधारभूत मामला है जो निरंतर समय लेता है।
एक पेड़ हमारे पास के रूप में इस मॉडलिंग:
T(N) = N -> T(N/2)
-> T(N/2)
= N -> (N/2) -> T(N/4)
-> T(N/4)
-> (N/2) -> T(N/4)
-> T(N/4)
यह तो सच में हम सिर्फ यह कितना गहरा हो जाता है देखने की जरूरत
T(N) = N + 2N/2 + 4N/4 + ...
= N + N + N ...
का एक विस्तार देता है। हम जानते हैं कि i वें स्तर आकार में subproblems N/2^i पर संचालित होता है। इसलिए हमारे पत्र-गांठ (T(1)) स्तर L जहां N/2^L = 1 पर पाए जाते हैं:
N/2^L = 1
N = 2^L
log N = log(2^L)
log N = L
इसलिए हमारे क्रम N log N है।
अब हम प्रविष्टि प्रकार का परिचय। हमारे पेड़ इस
T(N) = ... -> I(K)
-> I(K)
...x N/K
दूसरे शब्दों में कुछ ऐसी दिखाई देगी, हम कुछ स्तर L पर होगा आकार K की N/K प्रविष्टि प्रकार की समस्याओं को हल करने के लिए है। सम्मिलन क्रम में K^2 का सबसे खराब-केस रनटाइम है। तो पत्तियों पर हम कुल में इतना काम है:
(N/K) * I(K)
= (N/K) * K * K
= N * K
लेकिन हम भी पहले की तरह समझाया N पेड़ के स्तर प्रति की लागत से के रूप में अच्छी तरह से करने के लिए, विलय का एक समूह है। वापस हमारे पिछले विधि के लिए जा रहे है, चलो L लगता है (स्तरों की संख्या इससे पहले कि हम आकार K की subproblems तक पहुँचने और इस प्रकार प्रविष्टि करने के लिए स्विच) करते हैं:
N/2^L = K
N/K = 2^L
L = log (N/K)
तो कुल में हमारे पास
O(N) = N * K + N * log (N/K)
यह हो गया है बहुत लंबा है क्योंकि मैंने आपको सबूत स्केच देने के लिए एल्गोरिदम लिया था, लेकिन इसे आपके न्यूरॉन्स फायरिंग मिलनी चाहिए।