মার্জ সর্ট বিশ্লেষণ

Given that the merge function runs in $\mathrm{\Theta }(n)$‍ time when merging $n$‍ elements, how do we get to showing that mergeSort runs in $\mathrm{\Theta }(n{\log }_{2}n)$‍ time? We start by thinking about the three parts of divide-and-conquer and how to account for their running times. We assume that we're sorting a total of $n$‍ elements in the entire array.

যদি আমরা বিভক্তকরন এবং একত্রকরণ ধাপগুলোকে একসাথে চিন্তা করি তাহলে দেখা যায়, বিভক্তকরন ধাপের সময় $\mathrm{\Theta }(1)$‍ একত্রকরণ ধাপের সময় $\mathrm{\Theta }(n)$‍ থেকে কম। তাহলে, চিন্তা করে দেখ বিভক্তকরন এবং একত্রকরণ ধাপ একসাথে সম্পন্ন হতে $\mathrm{\Theta }(n)$‍ সময় নেয়। আরও ভালভাবে বোঝার জন্য, ধরি বিভক্তকরন এবং একত্রকরণ ধাপগুলো একসাথে সম্পন্ন হতে $cn$‍ সময় নেয় যেখানে $c$‍ একটি ধ্রুবক।

সহজভাবে বলা যায় যদি $n>1$‍ হয় তাহলে $n$‍ সর্বদা জোড় সংখ্যা হবে। অর্থাৎ যখন $n/2$‍ হয় তখন এটি একটি পূর্ণসংখ্যা হবে। (যেসব ক্ষেত্রে $n$‍ এর মান বিজোড় হয় সেসব ক্ষেত্রে big-Θ চিহ্নের জন্য মানের কোন পরিবর্তন হয় না)। তাহলে মার্জ সর্ট এর সময় $n$‍ উপাদান বিশিষ্ট সাবঅ্যারের জন্য হবে $(n/2)$‍ উপাদান বিশিষ্ট সাবঅ্যারের মার্জ সর্ট এর সময়ের সমষ্টির দ্বিগুণ (জয় ধাপ) যোগ $cn$‍ (বিভক্তকরন এবং একত্রকরণ ধাপ—শুধুমাত্র একত্রিত করার জন্য)।

এখন আমাদের $n/2$‍ উপদানের recursive calls (রিকারসিভ কল) এর রান করার সময় বের করতে হবে। প্রতিটি recursive calls এর রান করার সময় $(n/4)$‍ উপাদানবিশিষ্ট subarray (কেননা $n/2$‍ কে অর্ধেক করে ভাগ করতে হবে) এবং $cn/2$‍ এর মার্জ সর্ট করার দিগুন। আমাদের $n/2$‍ আকারের দুইটি ছোট সমস্যা আছে যার প্রতিটি মার্জ করার জন্য $cn/2$‍ সময় নেয়। সুতরাং $n/2$‍ আকারের ছোট সমস্যাগুলো মার্জ করতে সর্বমোট $2\cdot cn/2=cn$‍ সময় লাগে।

চল মার্জিং এর সময়গুলোকে "tree" (ট্রি) আকারে আকিঃ

কম্পিউটার বিজ্ঞানীরা বাস্তবিক trees বৃদ্ধি পাওয়ার বৈশিষ্টের উল্টো করে tree অঙ্কন করে। tree হচ্ছে এক ধরনের গ্রাফ যা চক্রাকার নয় (যার শুরু এবং শেষ একই জায়গায়)। প্রচলিত নিয়ম হল শীর্ষবিন্দুগুলো একটি ট্রিতে এর নোডসহ কল করা। মূল node(নোড) একদম শীর্ষে থাকে; এখানে, বাস্তব অ্যারে উপাদান $n$‍ এর জন্য মুলটি $n$‍ আকারের subarray দিয়ে লেবেল করা। মূল নোড এর নিচে দুইটি child nodes (চাইল্ড নোড) থাকে, যাদের প্রত্যেকে $n/2$‍ দিয়ে লেবেল করা এবং $n/2$‍ আকারের দুইটি ছোট সমস্যার জন্য সাবঅ্যারে কে প্রকাশ করে।

প্রতিটি $n/2$‍ আকারের ছোট সমস্যা $(n/2)/2$‍ অথবা $n/4$‍ আকারের দুইটি subarray কে রিকার্সিভ সর্ট করে। কেননা $n/2$‍ আকারের দুইটি এবং $n/4$‍ আকারের চারটি ছোট সমস্যা আছে। এই চারটি ছোট সমস্যার প্রতিটি সর্বমোট $n/4$‍ উপাদান মার্জ করে এবং চারটি ছোট সমস্যার প্রতিটির মার্জ করার সময় $cn/4$‍। চারটি subproblem কে একত্রিত করলে আমরা দেখতে পাই যে $n/4$‍ আকারের সবগুলো subproblem এর মার্জ করার সময় $4\cdot cn/4=cn$‍:

$n/8$‍ আকারের subproblem এর জন্য কি হতে পারে বলে তুমি ধারণা কর? সেখানে আটটি থাকবে যাদের প্রত্যেকটির মার্জিং এর সময় হবে $cn/8$‍ এবং মোট মার্জিং এর সময় হবে $8\cdot cn/8=cn$‍:

subproblems যত ছোট হতে থাকবে রিকার্সন এর প্রতিটি "লেভেল" এ subproblem এর সংখ্যা দিগুণ হতে থাকবে কিন্তু মার্জিং এর সময় অর্ধেক হয়ে যাবে। দিগুণ এবং অর্ধেক, এরা পরস্পরকে বাতিল করে দিবে এবং রিকার্সন এর প্রতিটি লেভেল এ মার্জিং সময় $cn$‍ হবে। ধীরে ধীরে, আমরা সাইজ 1 এর ছোট সমস্যাগুলোতে প্রবেশ করব: মূল সমস্যা। 1 আকারের subarray সর্ট করতে আমাদের $\mathrm{\Theta }(1)$‍ সময় ব্যয় করতে হবে, কেননা আমাদের পরীক্ষা করে দেখতে হবে $p<r$‍ এবং এই পরীক্ষার কত সময় দরকার। 1 আকারের, কতটি subarrays আছে? যেহেতু আমরা $n$‍ উপাদান নিয়ে শুরু করেছি সেহেতু এর উপাদান সংখ্যা অবশ্যই $n$‍ হবে। যেহেতু প্রতিটি বেস কেস এর জন্য $\mathrm{\Theta }(1)$‍ সময় দরকার হয় সেহেতু দ্মনে করে নেওয়া যায় যে বেস কেস এর জন্য $cn$‍ সময় দরকার হয়।

Now we know how long merging takes for each subproblem size. The total time for mergeSort is the sum of the merging times for all the levels. If there are $l$‍ levels in the tree, then the total merging time is $l\cdot cn$‍. So what is $l$‍? We start with subproblems of size $n$‍ and repeatedly halve until we get down to subproblems of size 1. We saw this characteristic when we analyzed binary search, and the answer is $l={\log }_{2}n+1$‍. For example, if $n=8$‍, then ${\log }_{2}n+1=4$‍, and sure enough, the tree has four levels: $n=8,4,2,1$‍. The total time for mergeSort, then, is $cn({\log }_{2}n+1)$‍. When we use big-Θ notation to describe this running time, we can discard the low-order term ($+1$‍) and the constant coefficient ($c$‍), giving us a running time of $\mathrm{\Theta }(n{\log }_{2}n)$‍, as promised.

মার্জ সর্ট সম্পরকে আরেকটি বিষয় গুরুত্বপূর্ণ। মার্জিং এর সময় এটি একটি সর্ট করা পূর্ণ array এর কপি করে রাখে যার এক অর্ধেক lowHalf অবস্থানে এবং অপর অর্ধেক highHalf অবস্থানে থাকে। এটি কিছু সময় বস্তুর উপাদানের ধ্রুবক সংখ্যা কপি করে, অর্থাৎ মার্জ সর্ট জায়গায় কাজ করে না । তুলনামুলকভাবে সিলেকশন সর্ট এবং ইনসারশন সর্ট সকল জায়গায় কাজ করে, কেননা তারা কখনও একই সময়ে একের অধিক উপদানের ধ্রুবক সংখ্যার কপি করে না। কম্পিউটার বিজ্ঞানীগণ এরকমভাবে চিন্তা করতে পচ্ছন্দ কর যে একটি অ্যালগোরিদম সঠিক জায়গাতে ঠিক মত কাজ করছে কিনা, কারণ আমাদের কিছু কিছু সিস্টেম আছে যার মধ্যে স্থান খুবই গুরুত্বপূর্ণ এবং তাই সঠিক স্থানে অ্যালগোরিদম থাকা গুরুত্বপূর্ণ।

এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।