প্রিফিক্স সাম হল একটি অ্যালগোরিদম, যা একটি অ্যারের উপাদানগুলোর যোগফল সংরক্ষণের একটি পদ্ধতি। এটি ব্যবহার করে, আমরা যেকোনো সাবঅ্যারে তে যোগফল বের করতে পারি অতি দ্রুত সময়ে।
প্রিফিক্স সাম কেন ব্যবহার করা হয়?
ধরি, আপনার কাছে একটি অ্যারে রয়েছে: [1, 2, 3, 4, 5]. এখন আপনি চাইতেছেন, arr[l] থেকে arr[r] পর্যন্ত যোগফল বের করতে। আপনি চাইলে অন্যভাবে খুব সহজেই করতে পারবেন কিন্তু অনলাইন জাজে Time Limit Exceed(TLE) খেতে পারেন। আর এই সমস্যা খুব সহজেই আপনি প্রিফিক্স সামের সাহায্যে সমাধান করতে পারবেন।
প্রিফিক্স সাম ব্যবহার না করলে আপনাকে প্রতি বার লুপ চালাতে হয়। কিন্তু যদি প্রিফিক্স সাম ব্যবহার করেন তাহলে একবার হিসাব করে, পরবর্তী সময়গুলোতে আপনি মাত্র O(1) সময়ে কাজটি করতে পারবেন।
প্রিফিক্স সামের সুবিধা :
প্রিফিক্স সামের সুবিধা হল যে এটি একবার অ্যারের উপাদানগুলোর যোগফল হিসাব করে সংরক্ষণ করে। যার পরবর্তী সময়ে সাবঅ্যারের যোগফল বের করার জন্য আমাদের সময় O(1) থাকে।
যেমনঃ, প্রিফিক্স সাম তৈরি করতে সময় লাগবে O(n), এবং সাবঅ্যারের যোগফল বের করতে O(1) সময় লাগে।
প্রিফিক্স সাম গণনার উদাহরণ :
C++ উদাহরণ
#include
using namespace std;
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = 5;
int prefix[n];
prefix[0] = arr[0]; // প্রথম উপাদান কপি করছি
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] + arr[i]; // প্রতিটি উপাদান যোগ করতে থাকছি
}
cout << "Prefix Sum Array: ";
for (int i = 0; i < n; i++) {
cout << prefix[i] << " "; // আউটপুট: 1 3 6 10 15
}
return 0;
}
Python উদাহরণ
def prefix_sum(arr):
prefix = [0] * len(arr)
prefix[0] = arr[0] # প্রথম উপাদান কপি করছি
for i in range(1, len(arr)):
prefix[i] = prefix[i - 1] + arr[i] # প্রতিটি উপাদান যোগ করতে থাকছি
return prefix
arr = [1, 2, 3, 4, 5]
print("Prefix Sum Array:", prefix_sum(arr)) # আউটপুট: [1, 3, 6, 10, 15]
কিভাবে সাবঅ্যারের যোগফল বের করা যাবে?
যদি আপনি জানেন যে আপনার প্রিফিক্স সাম অ্যারে তৈরি হয়ে গেছে, তাহলে আপনার সাবঅ্যারের যোগফল O(1) সময়ে বের করা যাবে। এই কোডটি দেখুন:
C++ উদাহরণ
int rangeSum(int prefix[], int l, int r) {
if (l == 0) return prefix[r];
return prefix[r] - prefix[l - 1]; // সাবঅ্যারের যোগফল বের করা
}
Python উদাহরণ
def range_sum(prefix, l, r):
if l == 0:
return prefix[r]
return prefix[r] - prefix[l - 1] # সাবঅ্যারের যোগফল বের করা
প্রিফিক্স সামের সুবিধা ও প্রয়োগ
প্রিফিক্স সামের সবচেয়ে বড় সুবিধা হলো, আপনি একবার যোগফল হিসাব করে সংরক্ষণ করে ফেললে, পরবর্তীতে সাবঅ্যারের যোগফল বের করতে মাত্র O(1) সময়ে কাজ করতে পারবেন। এতে আপনার প্রোগ্রাম আরও দ্রুত কাজ করবে।
প্রিফিক্স সাম ব্যবহার করে আপনি বিভিন্ন ধরনের সমস্যা যেমন, সাবঅ্যারের যোগফল, সাবঅ্যারের গড় বের করা, এবং অন্যান্য সংখ্যাসূচক সমস্যা সমাধান করতে পারবেন।
এই সর্টিং অ্যালগরিদমের মূল বিষয় হলো - একটি নির্দিষ্ট সংখ্যার জন্য এমন
একটি জায়গা খুঁজে বের করা যেখানে সংখ্যাটিকে রাখলে তার আগের সংখ্যাটি তার
থেকে ছোট বা সমান হবে এবং পরের সংখ্যাটি তার থেকে বড় হবে । তবে সংখ্যাটি
যদি অ্যাঁরে বা লিস্টের সবচেয়ে ছোট বা বড় সংখ্যা হয় তাহলে তার জন্য সবার
প্রথমে জায়গা করে দিতে হবে ।যেমন : - নিচের visualization টি লক্ষ্য করি :-
ধরি, আমাদের কাছে [10,30,40] এই অ্যাঁরেটি ছোট থেকে বড়
ক্রমে সাজানো আছে । আমি এই অ্যাঁরেতে আরেকটি সংখ্যা যুক্ত করতে চাই
সংখ্যাটি হলো 20 । এখন আমাকে 20 কে এমন এক জায়গায় বসাতে হবে যেখানে তার
আগের সংখ্যা তার থেকে ছোট বা সমান হবে এবং তার পরের সংখ্যাটি তার থেকে বড়
হবে ।
যদি অ্যাঁরেতে লক্ষ করি তাহলে দেখতে পারবো যে, সেই কাঙ্খিত জায়গাটি হচ্ছে 10
এর পরের অবস্থান কারণ, 20 থেকে 10 ছোট এবং 30 বড় । এখন যেহেতু 10 এর পরের
অবস্থানে 30 আছে, তাহলে 30 এর জায়গায় 20 কে বসাতে হলে অ্যাঁরের শেষ থেকে
অর্থাৎ 40 কে এক ঘর ডানে সরাতে হবে এখন 40 যেখানে ছিলো সেই ঘরটি কিন্তু
ফাকা -
[10, 30, _, 40]
এরপর 30 কে এক ঘর ডানে সরাই - [10, _, 30, 40]
এখন ফাকা জায়গাটি কিন্তু 20 এর জন্য পারফেক্ট জায়গা অর্থাৎ, যে স্থানটি
ফাকা তার আগের সংখ্যাটি 20 থেকে ছোট এবং পরের সংখ্যাটি 20 থেকে বড় । তাহলে
ফাকা জায়গাটিতে 20 কে এসাইন করি -
[10, 20, 30, 40]
এতক্ষণ যে পদ্ধতিতে একটি সংখ্যা অ্যাঁরেতে সাজানো হলো এই পদ্ধতিকেই আমরা ইনসারশন সর্ট(Insertion sort) বলতে পারি ।
অ্যারে(Array) ও ইনসার্শন সর্ট(Insertion sort) -
তো চলুন এখন একটি এলোমেলো অ্যাঁরে বা লিস্টকে ইনসারশন সর্ট(Insertion
sort) পদ্ধতিতে ছোট থেকে বড় ক্রমে বা Accending order এ সাজাই । ধরি, আমার
কাছে একটি অ্যারে আছে -
[50, 20, 10, 30]
স্টেপ(০১) :- প্রথমে 50 এবং 20 এর মধ্যে ছোট সংখ্যার জন্য
উপযুক্ত জায়গা খুঁজে বের করবো । এক্ষেত্রে, 20 কে 50 এর অবস্থানে বসাতে হবে
তাই 50 কে এক ঘর ডানদিকে সরাই । এখন কিন্তু 50 এর জায়গা খালি তাই খালি
জায়গায় 20 কে এসাইন করি -
[20, 50, 10, 30]
স্টেপ(০২) :- 50 এবং 10 এর মধ্যে 10 এর জন্য উপযুক্ত জায়গা
খুঁজে বের করি । এক্ষেত্রে, অ্যারের প্রথমে 10 কে রাখতে হবে অর্থাৎ 20 এর
অবস্থানে । তাই, প্রথমে 50 কে এক ঘর ডান দিকে সরাই - [20, _, 50, 30]
এখনও উক্ত ফাকা স্থানটি কিন্তু 10 এর উপযুক্ত জায়গা না তাই 20 কেও এক ঘর ডান দিকে সরাই - [_, 20, 50, 30]
এখন ফাকা স্থানে অর্থাৎ 20 এর আগের ঘরে 10 এসাইন করি -
[10, 20, 50, 30]
স্টেপ(০৩) :- 50 এবং 30 এর মধ্যে 30 এর জন্য উপযুক্ত জায়গা খুঁজে বের করি এক্ষেত্রে, 20 এবং 50 এর মাঝে । তাই 50 কে এক ঘর ডানদিকে সরাই -
[10, 20, _, 50]
এখন ফাকা জায়গাটিতে 30 কে এসাইন করি -
[10, 20, 30, 50]
ব্যাস, উপরোক্ত অ্যারে বা লিস্টটি ছোট থেকে বড় ক্রমে অর্থাৎ Accending
order এ সাজানো হয়ে গেলো । এখন আপনি যদি বুঝতে না পারেন তাহলে খাতা-কলম
নিয়ে বিষয়টি বোঝার চেষ্টা করতে পারেন । যদি প্রথম বা দ্বিতীয় বারে বিষয়টি
বুঝে থাকেন তাহলে আপনি একটি বড় অ্যারে বা লিস্টকে খাতা-কলমে সর্ট করতে
পারেন । তো চলুন এখন ইমপ্লিমেন্টেশন করা যাক -
In Python :
def insertionSort(arr):
for i in range(1, len(arr)):
# arr[i] কে currentValue তে এসাইন করি
currentValue = arr[i]
# currentValue এর জন্য উপযুক্ত স্থান খুঁজে বের করিj = i - 1# যদি j, 0 থেকে সমান বা বড় হয় এবং arr[j] থেকে currentValue ছোট হয়
while j >= 0and arr[j] > currentValue:
# arr[j] কে তার পরের ঘরে রেখে দিই
arr[j+1] = arr[j]
# j এর মান 1 করে কমাইj -= 1# এখন খালি জায়গায় currentValue কে বসাই
arr[j+1] = currentValue
return arr
In JavaScript :
function insertionSort(arr) {
// একটি currentValue নামে ভেরিয়েবল নিই
var currentValue;
// i এর মান 1 থেকে len(arr) এর আগ পর্যন্ত 1 করে বাড়াই
for (var i = 1; i < arr.length; i++) {
// arr[i] কে currentValue তে এসাইন করি
currentValue = arr[i];
// currentValue এর জন্য উপযুক্ত স্থান খুঁজে বের করি (j = i - 1)
// যদি j, 0 থেকে সমান বা বড় হয় এবং arr[j] থেকে currentValue ছোট হয়
for (var j = i - 1; j >= 0 && arr[j] > currentValue; j--) {
// arr[j] কে তার পরের ঘরে রেখে দিই
arr[j + 1] = arr[j];
}
// এখন খালি জায়গায় currentValue কে বসাই
arr[j + 1] = currentValue;
}
return arr;
}
আপনি চাইলে জাভাস্ক্রিপ্ট কোডে for লুপের পরিবর্তে while লুপ ব্যাবহার করতে পারেন ।
উপরোক্ত কোড বিশ্লেষণ :-
উপরের প্রোগ্রামে, প্রথমে i=1 থেকে অ্যারের লেন্থ পর্যন্ত
লুপ চালিয়েছি । তারপর currentValue নামে একটি ভেরিয়েবলের মাঝে অ্যারের
Present ভ্যালুকে রাখছি । এক্ষেত্রে কারেন্ট ভ্যালুটি যাতে হারিয়ে না যায়
তা নিশ্চিত করছি কারণ পরবর্তীতে এই currentValue কেই তার যথাযথ স্থানে
রাখতে হবে ।
তারপর ভেতরের লুপে j >= 0 এবং arr[j] > currentValue
এইভাবে চেক করতেছি । এখানে, যদি j এর মান 0 থেকে ছোট হয় তাহলে আমি বুঝতে
পারবো যে অ্যারে বা লিস্টের সব উপাদানই currentValue থেকে বড় । আবার, j এর
মান যদি 0 থেকে বড় বা সমান হয় তাহলে দ্বিতীয় শর্তপরীক্ষা করা করবো অর্থাৎ
arr[j] > currentValue ।
এখন যদি দ্বিতীয় শর্ত অর্থাৎ arr[j] > currentValue সত্য হয় তাহলে, arr[j] কে আমরা এক ঘর ডানে সরিয়ে দিব - arr[j + 1] = arr[j]
আবার, arr[j] > currentValue যদি মিথ্যা হয় তাহলে, লুপ থেকে বের হয়ে
arr[j + 1] এ currentVal কে এসাইন করে দিব - arr[j + 1] = currentVal
ইত্যাদি ।
যেকোনো অ্যালগরিদম বাঁ ডাটা-স্ট্রাকচারের মূল কনসেপ্ট যদি আপনি ভালোভাবে
বুঝতে পারেন তাহলে যেকোনো প্রোগ্রামিং ল্যাঙ্গুয়েজ ব্যাবহার করেই
ইমপ্লিমেন্ট করতে পারবেন । চলুন ইনসার্শন সর্ট(Insertion sort)
অ্যালগরিদমের টাইম ও স্পেস কমপ্লেক্সিটি বের করা যাক -
টাইম কমপ্লেক্সিটি(Time Complexity) :
উপরোক্ত কোড লক্ষ করলে আশা করি টাইম কমপ্লেক্সিটি(Time Complexity) বলে
দিতে পারবেন । এই অ্যালগোরিদমেরও টাইম কমপ্লেক্সিটি(Time Complexity) O(n2) ।
স্পেস কমপ্লেক্সিটি(Space Complexity) :
উপরের প্রোগ্রামে একটু খেয়াল করলে দেখতে পারবো যে, প্রোগ্রামে একটি
লিস্ট বা অ্যারে প্যারামিটার হিসেবে নেওয়া হয়েছে । এবং যা কাজ-কারবার করা
হয়েছে তা এই অ্যারে বা লিস্টের মধ্যেই । এই অ্যারে বা লিস্টে কিন্তু কোনো
নতুন উপাদান সংযোজন, বিয়োজন ইত্যাদি কিছুই করা হয় নাই । তাহলে বলতে পারি
অ্যারে বা লিস্টটি Constant । এখন আপনার কাছে আমার প্রশ্ন এই প্রোগ্রামের
স্পেস কমপ্লেক্সিটি(Space Complexity) কত ?
ব্রাভো, যদি এতদূর পর্যন্ত আপনি ঠিকঠাক ভাবে পড়ে থাকেন তাহলে আমি ধরে
নিতেই পারি ইনসার্শন সর্ট(Insertion sort) অ্যালগরিদম সম্পর্কে ভালো একটা
দখল চলে আসছে ।
যদি সত্যি বুঝে থাকেন তাহলে একটি কাজ করতে পারেন, উপরোক্ত অ্যারেটিকে
আমি কিন্তু Accending Order অর্থাৎ ছোট থেকে বড় ক্রমে সাজিয়েছি এখন আপনি
ইনসার্শন সর্ট(Insertion sort) অ্যালগরিদম ব্যাবহার করে অ্যারেটিকে
Decending Order অর্থাৎ বড় থেকে ছোট ক্রমে সাজানোর চেষ্টা করবেন ।
খুবই সহজ একটি কাজ আশা করি পারবেন শুভকামনা রইলো ।
