এখানে আমরা দেখব কিভাবে পুনরাবৃত্ত সম্পর্ক সমাধান করতে প্রতিস্থাপন পদ্ধতি ব্যবহার করতে হয়। এটাকে আরও ভালোভাবে বোঝার জন্য আমরা দুটি উদাহরণ দেব।
ধরুন আমরা বাইনারি সার্চ টেকনিক ব্যবহার করছি। এই কৌশলটিতে, আমরা উপাদানটি শেষে উপস্থিত আছে কিনা তা পরীক্ষা করি। যদি এটি মাঝখানে উপস্থিত থাকে, তাহলে অ্যালগরিদম বন্ধ হয়ে যায়, অন্যথায় আমরা প্রকৃত অ্যারে থেকে বাম এবং ডান সাবয়ারে বারবার গ্রহণ করি। সুতরাং প্রতিটি ধাপে অ্যারের আকার n / 2 দ্বারা হ্রাস পায়। ধরুন বাইনারি অনুসন্ধান অ্যালগরিদমটি কার্যকর করতে T(n) পরিমাণ সময় নেয়। বেস কন্ডিশন O(1) পরিমাণ সময় নেয়। সুতরাং পুনরাবৃত্তি সমীকরণটি নীচের মত হবে −
$$T(n)=\begin{cases}T(1) &for\:n \leq 1\\2T(\frac{n}{2})+c &for\:n> 1\end{কেস }$$
সমাধান করুন −
ফলাফল পেতে আমরা প্রতিটি ধাপে সূত্রটি প্রতিস্থাপন করব$$T(n)=T(\frac{n}{2})+c$$
T(N/2) প্রতিস্থাপন করে আমরা লিখতে পারি,
$$T(n)=(T(\frac{n}{4})+c)+c$$
$$T(n)=T(\frac{n}{4})+2c$$
$$T(n)=T(\frac{n}{8})+3c$$
$$T(n)=T(\frac{n}{2^{k}})+kc$$
এখন যদি $$(\frac{n}{2^{k}})$$ 1 এ পৌঁছায়, এটি নির্দেশ করে যে 2 k হল n. সুতরাং k এর মান হল log2 𝑛
T(n) =ϴ(log n)
এর জটিলতাএকইভাবে, আমরা যদি মার্জ সর্টের মতো আরেকটি উদাহরণ বেছে নিই, তাহলে সেই ক্ষেত্রে আমরা তালিকাটিকে দুটি ভাগে ভাগ করি। তালিকার আকার মাত্র 1 না হওয়া পর্যন্ত এই বিভাগটি সংঘটিত হচ্ছে। এর পরে আমরা তাদের সাজানো ক্রমে একত্রিত করি। মার্জিং অ্যালগরিদম O(n) পরিমাণ সময় নেয়। সুতরাং মার্জ সর্ট অ্যালগরিদম যদি T(n) পরিমাণ সময় নেয়, তাহলে এটিকে দুটি অর্ধে ভাগ করে, এবং তাদের প্রত্যেকের জন্য একই কাজ করে, তারা T(n/2) এবং আরও অনেক কিছু নেবে। সুতরাং পুনরাবৃত্তি সম্পর্ক নীচের মত হবে −
$$T(n)=\begin{cases}T(1) &for\:n =1\\2T(\frac{n}{2})+cn &for\:n> 1\end{cases} $$
সমাধান করুন −
ফলাফল পেতে আমরা প্রতিটি ধাপে সূত্রটি প্রতিস্থাপন করব$$T(n)=2T(\frac{n}{2})+cn$$
T(N/2) প্রতিস্থাপন করে আমরা লিখতে পারি,
$$T(n)=2(2T(\frac{n}{4})+\frac{cn}{2}) +cn$$
$$T(n)=4T(\frac{n}{4}) +2cn$$
$$T(n)=8T(\frac{n}{8}) +3cn$$
$$T(n)=2^{k}T(\frac{n}{2^{k}}) +kcn$$
এখন যদি $$(\frac{n}{2^{k}})$$ 1 এ পৌঁছায়, এটি নির্দেশ করে যে 2 k হল n. সুতরাং k এর মান হল log2 𝑛 এবং T(n) হবে −
𝑇(𝑛) =𝑛𝑇(1) + 𝑐𝑛 লগ2 𝑛
জটিলতা হল θ(n log n)
