मर्ज-सॉर्ट एल्गोरिथ्म के निम्नलिखित रूप के बारे में:
public static void merge(int [] a, int ini, int med, int end){
int [] b = new int[end - ini + 1];
int i = ini;
int j = med + 1;
int k = 0;
while(i <= med && j <= end) {
if(a[i] <= a[j]){
b[k] = a[i];
i++;
}
else {
b[k] = a[j];
j++;
}
k++;
}
while(i <= med) {
b[k] = a[i];
i++;
k++;
}
while(j <= end) {
b[k] = a[j];
j++;
k++;
}
for(k = 0; k < b.length; k++){
a[ini + k] = b[k];
}
}
public static void mergeSortRec(int [] a, int ini, int end){
if(ini < end){
int med = (ini + end) / 2;
mergeSortRec(a, ini, med);
mergeSortRec(a, med + 1, end);
merge(a, ini, med, end);
}
}
public static void mergeSort(int [] a){
mergeSortRec(a, 0, a.length - 1);
}
मुझे यह पहचानना होगा कि मर्ज विधि में क्या अंतर होगा अगर मैं मर्ज को अंदर से परिवर्तित कर दूं।
मैंने एल्गोरिथ्म का मूल्यांकन करने की कोशिश की,और पता चला कि पूर्व में मर्ज O (n) में चला जाता है और mergeSortRec O (ln n) के रूप में चला जाता है (इसलिए एल्गोरिथ्म एक O (n ln n) है, लेकिन मैं मूल्यांकन नहीं कर सका कि यह नए रूप में कैसे खड़ा है) ।
जब परिवर्तन किया जाता है तो मर्ज विधि के प्रदर्शन में क्या अंतर होता है? एक पूरे के रूप में एल्गोरिथ्म के लिए, क्या कोई वास्तविक अंतर है?
मैं यह देखने का प्रयास कर रहा हूं कि दोनों में से कौन अधिक कुशल होगा (मुझे पता है कि यह शायद n / 2 एक है) एक अभ्यास के रूप में, लेकिन मैं इसका मूल्यांकन करने में सक्षम नहीं हूं
उत्तर:
उत्तर № 1 के लिए 1यदि आप समस्या को दो भागों में तोड़ते हैं (बजाय इसकेदो बराबर भाग) एक हिस्सा प्रारंभिक के एक चौथाई और दूसरा (3/4) मूल समस्या का है, तो आपका पुनरावर्तन वृक्ष दूसरे भाग के लिए और गहरा हो जाएगा और इसलिए यह चलने के समय को बढ़ाएगा।
नीचे अंतर्निहित गणित है-
T (N) = T (N / 4) + T (3 * N / 4)
= T(N/16) + T(3*N/16) + T(3*N/16) + T(9*N/16)
= T(N/16) + 2*T(3*N/16) + T(N*(3/4)*(3/4))
...
...
यहां से आप देख सकते हैं कि पुनरावर्ती कॉल समाप्त हो जाएंगे जब (3/4) की कुछ शक्ति एन के बराबर या उससे अधिक होगी।
(3/4) ^ x = N
x = log 3/4 आधार पर
अब आप 2 बेस पर logN के ग्राफ की तुलना कर सकते हैं और 3/4 बेस पर logN कर सकते हैं और समझ सकते हैं कि दो समान भागों में विभाजित होने के कारण विषम स्पर्शोन्मुख व्यवहार क्यों होता है।
यह आपके मध्य ini + (अंत- ini) / 4 के साथ आकार 16 की एक सरणी के लिए पुनरावर्तन वृक्ष है
अनुलेख अनिमिपोटिक विश्लेषण समझने के लिए पाठ्य पुस्तकें पढ़ें। यह आपकी बहुत मदद करेगा।