কিভাবে মার্জ সাজানোর জটিলতা গণনা করা হয়?

2024 লেখক: Lynn Donovan | [email protected]. সর্বশেষ পরিবর্তিত: 2023-12-15 23:44

2 উত্তর। একটি নোড A[L, R] কে দুটি নোডে বিভক্ত করতে R−L+1 সময় লাগে এবং তারপর মার্জ দুটি চাইল্ড নোড A[L, M] এবং A[M+1, R] আবার A[R−L+1] সময় নেয়। এইভাবে প্রতিটি নোডের জন্য, অপারেশন সংখ্যা অ্যালগরিদম যে নোডের সাথে সংশ্লিষ্ট অ্যারের আকারের দ্বিগুণের সমান পারফর্ম করে।

এই বিষয়ে, কিভাবে মার্জ সাজানোর কাজ করে?

এখানে কিভাবে মার্জ সর্ট ডিভাইড-এন্ড-কনকার ব্যবহার করে:

1. p এবং r এর মাঝপথে অবস্থানের q সংখ্যাটি খুঁজে বের করে ভাগ করুন।
2. বিভাজন ধাপ দ্বারা তৈরি দুটি উপ-সমস্যাগুলির প্রতিটিতে সাব্যারেগুলিকে পুনরাবৃত্তিমূলকভাবে বাছাই করে জয় করুন।
3. দুটি সাজানো সাবয়ারে আবার একক সাজানো সাবয়ারে অ্যারেতে মার্জ করে একত্রিত করুন[p..

এছাড়াও, মার্জ সাজানোর জন্য বড় হে জটিলতা কি? মার্জ সাজান একটি স্থিতিশীল হয় সাজান যার মানে হল যে একটি অ্যারের একই উপাদান একে অপরের সাথে তাদের আসল অবস্থান বজায় রাখে। সামগ্রিক সময় জটিলতা এর মার্জ সাজান হয় ও (nLogn)। এটি আরও দক্ষ কারণ এটি সবচেয়ে খারাপ ক্ষেত্রেও রানটাইম ও (nlogn) স্থান জটিলতা এর মার্জ সাজান হয় ও (n)

সবচেয়ে খারাপ ক্ষেত্রে মার্জ সাজানোর জটিলতা কি?

n*লগ(n)

মার্জ সাজানোর কয়টি তুলনা হয়?

যখন আমাদের একটি তালিকার উপাদানগুলি শেষ হয়ে যায়, তখন আমরা অবশিষ্ট উপাদানগুলিকে তালিকার শেষ স্লটে রাখি সাজানো তালিকা ফলে, মার্জ দুটি তালিকা যার মোট n উপাদান আছে সর্বাধিক n-1 প্রয়োজন তুলনা.