README
🌟 Time Complexity & Asymptotic Notation: টাইম কমপ্লেক্সিটি শুনে আমাদের প্রথমে মনে হতে পারে, আমাদের কোড রান হতে কত সময় নেয় তার একটি মেজারমেন্ট। ব্যাপারটি আসলে তা না। একটি কোড রান হতে কত সময় লাগছে তা আমরা কখনো হিসাব করি না। কারণ সেইম কোড উইন্ডোজে রান করতে যত সময় লাগছে ম্যাক এ রান হতে তত সময় নাও লাগতে পারে। আবার 32-bit উইন্ডোজে যত সময় লাগছে 64-bit উইন্ডোজে হয়তো তার থেকে কম লাগতে পারে। এখন তাহলে আমরা কিভাবে পরিমাপ করব কোন কোডটি ফাস্ট এবং কোন কোডটি স্লো। এই পরিমাপটিই হচ্ছে টাইম কমপ্লেক্সিটি। টাইম কমপ্লেক্সিটিতে আমরা ইনপুট এর প্রেক্ষিতে operation নাম্বার কিরকম হতে পারে তা মেজার করি।
আমাদের কোডটি যদি হয় এরকমঃ
for(int i=0; i<n; i++)
{
cout << "Hello" << endl;
}
এক্ষেত্রে ইনপুট n এর মান যদি ১০ হয় তাহলে কোডটি ১০ বার হ্যালো প্রিন্ট করবে। অর্থাৎ ১০ বার প্রিন্ট অপারেশন চালাবে। তেমনি ইনপুট n এর মান যদি ১০০০০০০ (১০ লক্ষ বার) হয় তাহলে কোডটি ১০ লক্ষ বার হ্যালো প্রিন্ট করবে। এই যে ইনপুট এর মানের সাথে কোডের অপারেশনের একটি সম্পর্ক এটিই পরিমাপ করা হয় টাইম কমপ্লেক্সিটিতে।
🔹 Asymptotic Notation: টাইম কমপ্লেক্সিটির একক বলা যায় Asymptotic Notation কে। মূলত ৩ ধরনের Asymptotic Notation রয়েছে।
Big O Notation - Worst case
Theta Notation - Average case
Omega Notation - Best case
মনে করি আমার কাছে ১০০টি সংখ্যা রয়েছে। সেখান থেকে আমি একটি নির্দিষ্ট সংখ্যাকে খুঁজছি। তাহলে অবশ্যই আমাকে প্রথম থেকে এক এক করে সবগুলো সংখ্যা খুঁজে দেখতে হবে। এখন আমি যদি প্রথম বার খুঁজতে যেয়েই আমার কাঙ্খিত সংখ্যাটি পেয়ে যাই তাহলে সেটিকে বেস্ট কেস বলা যায়। আমি যদি ৫০বার খোঁজার পর আমার সংখ্যাটি পাই তাহলে এভারেজ কেস বলতে পারি। এবং আমি যদি সবগুলো সংখ্যা খোঁজা শেষে (১০০ বার) একদম লাস্টে যেয়ে আমার সংখ্যাটি পাই তাহলে সেটিকে worst কেস বলা যেতে পারে।
টাইম কমপ্লেক্সিটি ক্যালকুলেট করার সময় আমরা সবসময় worst কেসটা নেই।
🔹 টাইম কমপ্লেক্সিটি কেন প্রয়োজন: মনে করি, আমরা দুজন স্টুডেন্টকে একটি প্রবলেম দিলাম। প্রবলেমটি হলো ১ থেকে n পর্যন্ত যোগ করতে হবে। এখন একজন স্টুডেন্ট n ইনপুট নেওয়ার পর ১ থেকে n পর্যন্ত লুপ চালিয়ে যোগফল বের করল। আরেকজন স্টুডেন্ট n∗(n+1)/2 (১ থেকে n পর্যন্ত স্বাভাবিক সংখ্যার যোগফল এর সূত্র) দিয়ে করে ফেলল। এখন আমাদের যদি বের করতে হয় কার কোডটি বেটার, তাহলে আমাদের দুজনের কোডের কমপ্লেক্সিটি বের করতে হবে। এক্ষেত্রে দুজনের কোডই কারেক্ট অ্যান্সার দিবে কিন্তু প্রথম স্টুডেন্ট এর কোড n পর্যন্ত লুপ চালিয়ে যোগ করবে। n এর মান যদি হয় ১০,০০০ তাহলে প্রথম স্টুডেন্ট এর কোড ১০,০০০টি অপারেশন চালাবে। অপরদিকে দ্বিতীয় স্টুডেন্ট, যে সূত্র দিয়ে করেছে তার কোড মাত্র ১টি অপারেশন চালাবে। অবশ্যই দ্বিতীয় স্টুডেন্ট এর কোড বেটার। এটি আমরা বলতে পারলাম টাইম কমপ্লেক্সিটির সাহায্যে।
🌟 O(N) টাইম কমপ্লেক্সিটি: O(N) টাইম কমপ্লেক্সিটিকে বলা হয় লিনিয়ার টাইম কমপ্লেক্সিটি। ইনপুটের সাপেক্ষে আমাদের প্রোগ্রামের অপারেশন যদি সমান ভাবে বাড়তে থাকে তবে সেই কমপ্লেক্সিটিকে আমরা বলতেছি লিনিয়ার টাইম কমপ্লেক্সিটি বা O(N) টাইম কমপ্লেক্সিটি। আরেকটু ক্লিয়ার করে বললে, আমার প্রোগ্রামে যদি এমন কোনো ইন্সট্রাকশন থাকে যা একটি ভেরিয়েবল ইনপুট N এর উপর নির্ভর করে অর্থাৎ N এর ভ্যালু ১০ হলে কাজটি ১০ বার সম্পাদন হয়, N এর ভ্যালু ১০০ হলে কাজটি ১০০ বার সম্পাদন হয়, N এর ভ্যালু ১০০০ হলে কাজটি ১০০০ বার সম্পাদন হয় সেই ক্ষেত্রে আমরা বলতে পারি, আমাদের কোডটির টাইম কমপ্লেক্সিটি O(N)।
চলুন, কিছু কোডের উদাহরণ দেখে বিষয়টি আরো ভালোভাবে বোঝার চেষ্টা করি।
🔹 Problem 1:
int n; cin >> n;
for(int i = 0; i < n; i++){ cout << i << endl; }
// Input : 10 // Output : 0 1 2 3 4 5 6 7 8 9 উপরোক্ত কোডে নিচের for লুপটি ঠিক কতবার চলবে আমরা তা প্রোগ্রাম এ ইনপুট দেওয়ার আগে বলে দিতে পারব না। এখানে লুপটি কতবার চলবে, এবং এর মধ্যে দেওয়া প্রিন্ট ইন্সট্রাকশন টি কতবার সম্পাদন হবে তা সম্পূর্ণ নির্ভর করছে একটি ভেরিয়েবল N এর উপর। সুতরাং এই কোডের টাইম কমপ্লেক্সিটি হবে O(N)।
🔹 Problem 2:
int n; cin >> n;
for(int i = 0; i < n; i+=2){ cout << i << " "; }
// Input : 10 // Output : 0 2 4 6 8 10 এই প্রবলেমের জন্য যদি আমরা N এর ভ্যালু ১০ ধরে নিই, তবে প্রথমে লুপটি তে i এর মান শুরু হবে ০ হতে। এরপরের স্টেপ এ i এর মান হয়ে যাবে ২, এরপর ৪, এরপর ৬, এরপর ৮ এবং এর পরের স্টেপ এ i এর মান ১০ হয়ে যাবে এবং কন্ডিশন মিথ্যা হয়ে যাওয়ার কারণে লুপ টি ব্রেক করবে। আমরা যদি একটু খেয়াল করে দেখি সর্বমোট ৫ বার লুপের ভিতরের কাজটি সম্পাদন হয়েছে, যা আসলে ১০ এর অর্ধেক। যদি N এর ভ্যালু হতো ১০০ তবে কাজটি সম্পাদন হতো ১০০ এর অর্ধেক অর্থাৎ ৫০ বার। তার মানে আমরা বলতে পারি এই কোডের টাইম কমপ্লেক্সিটি হবে O(N/2)। কিন্তু আমরা পূর্বের মডিউলে দেখে এসেছি, টাইম কমপ্লেক্সিটি নির্ণয়ের সময় আমরা সর্বদা ধ্রুবক যে অংশটুকু আছে তা বাদ দিয়ে দিব। সুতরাং এই কোডের টাইম কমপ্লেক্সিটি হবে O(N)।
🔹 Problem 3 (Reversing an Array):
for(int i = 0; i < n/2; i++){
int temp = a[i];
a[i] = a[n-i-1];
a[n-i-1] = temp;
}
উপরের কোড দ্বারা আমরা একটি N সাইজের এরে কে রিভার্স করতে পারি। এখানে যদি খেয়াল করে দেখি, এরে এর সাইজ যত হবে লুপটি তার অর্ধেক পরিমাণ চলবে। এবং সাথে সাথে এরেটি রিভার্স হয়ে যাবে। যেহেতু N এর অর্ধেক পরিমাণ ইন্সট্রাকশন এখানে সম্পাদন হচ্ছে, তাই Problem 2 এর মতো এই কোডের ও টাইম কমপ্লেক্সিটি হবে O(N)।
🔹 Problem 4:
// loop 1:
for(int i = 1; i <= n; i++){
cout << i << " ";
}
cout << endl;
// loop 2: for(int j = 1; j <= m; j++){ cout << j << " "; }
// Input : 10 5 // Output : // 1 2 3 4 5 6 7 8 9 10 // 1 2 3 4 5 উপরের কোডে প্রথম লুপটি মোট N বার চলবে এবং তা শেষ হলে দ্বিতীয় লুপটি মোট M বার চলবে। ধরি, N এর মান ১০, এখন উপরের লুপটি ১০ বার চলবে, এরপর ধরি, M এর মান ৫, এখন দুই নাম্বার লুপটি ৫ বার চলবে। সুতরাং পুরো প্রোগ্রাম এ সর্বমোট ১০+৫ = ১৫ টি কাজ সম্পাদন হচ্ছে। এখানে লক্ষ্য করে দেখা যায়, যদি আমরা পুরা কোড বিবেচনা করি তবে সর্বমোট আসলে কতটি কাজ সম্পাদন হচ্ছে তা হচ্ছে N এবং M এর যোগфলের সমান। সুতরাং এই কোডের টাইম কমপ্লেক্সিটি হলো O(N+M)।
🔹 সহজে মনে রাখার উপায়ঃ আমার প্রোগ্রামে যদি এমন কোনো ইন্সট্রাকশন থাকে যা একটি ভেরিয়েবল ইনপুট N এর উপর নির্ভর করে অর্থাৎ N এর ভ্যালু ১০ হলে কাজটি ১০ বার সম্পাদন হয়, N এর ভ্যালু ১০০ হলে কাজটি ১০০ বার সম্পাদন হয়, N এর ভ্যালু ১০০০ হলে কাজটি ১০০০ বার সম্পাদন হয় সেই ক্ষেত্রে আমরা বলতে পারি, আমাদের কোডটির টাইম কমপ্লেক্সিটি O(N)।
🌟 O(logN) টাইম কমপ্লেক্সিটি: O(logN) টাইম কমপ্লেক্সিটিকে বলা হয় লগারিদমিক টাইম কমপ্লেক্সিটি। ইনপুটের বৃদ্ধির সাপেক্ষে আমাদের প্রোগ্রামের অপারেশন যদি একটি নির্দিষ্ট বেস এর লগারিদমিক হারে কমতে থাকে সেই কমপ্লেক্সিটি কে আমরা বলতেছি লগারিদমিক টাইম কমপ্লেক্সিটি বা O(logN) টাইম কমপ্লেক্সিটি। যেমন ধরুন, আমাদের প্রোগ্রামে যদি এমন কোনো ইন্সট্রাকশন থাকে যা একটি ভেরিয়েবল ইনপুট N এর লগারিদমিক মান এর উপর নির্ভর করে অর্থাৎ N এর ভ্যালু ১০ হলে কাজটি কম বেশি log 10 ∼৩ বার সম্পাদন হয়, N এর ভ্যালু ১০০ হলে কাজটি কম বেশি log 100 ∼৬ বার সম্পাদন হয়, N এর ভ্যালু ১০০০০ হলে কাজটি কম বেশি log 1000 ∼৯ বার সম্পাদন হয় সেই ক্ষেত্রে আমরা বলতে পারি, আমাদের কোডটির টাইম কমপ্লেক্সিটি O(logN)। খেয়াল করে দেখবেন, এইক্ষেত্রে আমাদের কোডের টাইম কমপ্লেক্সিটি আগের মডিউলের টাইম কমপ্লেক্সিটি O(N) এর মতো ইনপুটের সাথে সাথে সমান হারে বাড়ছে না।
চলুন, কিছু কোডের উদাহরণ দেখে বিষয়টি আরো ভালোভাবে বোঝার চেষ্টা করি।
🔹 Problem 1:
int n; cin >> n;
for(int i = n; i > 1; i = i/2){ cout << i << endl; }
// Input : 100 // Output : 100 50 25 12 6 3 চলুন, উপরের কোডে লুপ টি কয়বার চলবে তা আমরা একটি উদাহরণের সাহায্যে দেখার চেষ্টা করি। ধরেন, N এর মান ১০০। প্রথমে লুপ ১০০ (১ নং) থেকে শুরু হবে, এরপর ১০০/২ = ৫০ (২ নং) -> ৫০/২ = ২৫ (৩ নং) -> ২৫/২ = ১২ (৪ নং) -> ১২/২ = ৬ (৫ নং) -> ৬/২ = ৩ (৬ নং) -> ৩/২ = ১, এখানে লুপ টি থেমে যাবে। দেখা যাচ্ছে এখানে সর্বমোট ৬ বার লুপ টি চলেছে। দেখা যাচ্ছে ১০০ কে ২ দিয়ে যতবার ভাগ করা যাচ্ছে ঠিক তত সংখ্যক বার লুপটি চলছে। আর একটি সংখ্যা N কে ২ দিয়ে কতবার ভাগ করা যাবে তা আমরা প্রকাশ করি logN দ্বারা। তাই এই কোডের টাইম কমপ্লেক্সিটি হলো O(logN)।
🔹 Problem 2:
int n; cin >> n;
for(int i = 1; i < n; i = i*2){ cout << i << endl; }
// Input : 100 // Output : 1 4 8 16 32 64 কিছু উদাহরণের সাহায্যে আমরা N এবং এই কোডের লুপ সংখ্যার সাথে তা বের করার চেষ্টা করব। ধরেন N এর মান হলো ১০। এখন i=১ থেকে শুরু হবে, ১২ = ২ (২ বার) -> ২২ = ৪ (৩ বার) -> ৪২ = ৮ (৪ বার) -> ৮২ = ১৬ > ১০, লুপটি এখানে থেমে যাবে। সুতরাং সর্বমোট log10∼৩ বার এই লুপটি চলেছে। এরপর আসেন, N এর মান ১০০ এর জন্য টেস্ট করে দেখি বিষয় টি। i=১, থেকে শুরু হবে এরপর ১২ = ২ (২ বার) -> ২২ = ৪ (৩ বার) -> ৪২ = ৮ (৪ বার) -> ৮২ = ১৬ (৫ বার) -> ১৬২ = ৩২ (৬ বার) -> ৩২২ = ৬৪ (৭ বার) -> ৬৪*২=১২৮>১০০ এখানে লুপটি থেমে যাবে। সুতরাং সর্বমোট log100∼৬ বার লুপটি চলেছে। সবশেষে এখান থেকে আমরা বুঝতে পারতেছি যে কোন একটি সংখ্যাকে ম্যাক্সিমাম কয়বার ২ দিয়ে গুণ করা যাবে যাতে করে তা N এর থেকে ছোট হয় / সমান হয়, তা হলো ঐ সংখ্যার লগের সমান অর্থাৎ logN এর সমান। তাই উপরের কোডের টাইম কমপ্লেক্সিটি হচ্ছে O(logN)।
🔹 Problem 3:
k = 2;
for(int i = 0; i < n; i++){
i *= k;
}
উপরের কোড এ আমাদের মনে হতে পারে, লুপটি তে যেহেতু i এর মান ০ থেকে শুরু হয়ে N এর আগ পর্যন্ত যাচ্ছে এবং প্রত্যেক ক্ষেত্রে i++ হচ্ছে তাই হয়তো এর কমপ্লেক্সিটি O(N) এর সমান। কিন্তু ভিতরের ইন্সট্রাকশন এ লক্ষ্য করলে দেখা যায়, সেখানে i এর মানের সাথে প্রত্যেকবার ২ গুণ হচ্ছে। এবং উপরের প্রবলেম থেকে জেনে এসেছি, কোন একটি সংখ্যাকে ম্যাক্সিমাম কয়বার ২ দিয়ে গুণ করা যাবে যাতে করে তা N এর থেকে ছোট হয় / সমান হয়, তা হলো ঐ সংখ্যার লগের সমান অর্থাৎ logN এর সমান। তাই এই কোডের টাইম কমপ্লেক্সিটি হবে O(logN)।
🔹 সহজে মনে রাখার উপায়ঃ যখন আমাদের কোডে কোন একটি লুপের key variable যেমন i এর মান যদি দ্বিগুণ হারে বাড়তে থাকে অথবা i এর মান প্রতিক্ষেত্রে অর্ধেক হয়ে কমতে থাকে, সেই ক্ষেত্রে আমরা বলতে পারি আমাদের কোডের টাইম কমপ্লেক্সিটি হলো O(logN)।
🌟 O(sqrt(N)) টাইম কমপ্লেক্সিটি: O( N
) টাইম কমপ্লেক্সিটিকে বলা হয় স্কয়ার রুট টাইম কমপ্লেক্সিটি। ইনপুটের বৃদ্ধির সাপেক্ষে আমাদের প্রোগ্রামের অপারেশন যদি তার বর্গমূলের / রুটের সমান হয় সেই কমপ্লেক্সিটি কে আমরা বলতেছি স্কয়ার রুট টাইম কমপ্লেক্সিটি বা O( N
) টাইম কমপ্লেক্সিটি। যেমন ধরুন, আমাদের প্রোগ্রামে যদি এমন কোনো ইন্সট্রাকশন থাকে যা একটি ভেরিয়েবল ইনপুট N স্কয়ার রুটের / বর্গমূল কাছাকাছি কোন মান হয় অর্থাৎ N এর ভ্যালু ১০ হলে কাজটি কম বেশি
10
∼৩ বার সম্পাদন হয়, N এর ভ্যালু ১০০ হলে কাজটি কম বেশি
100
∼১০ বার সম্পাদন হয়, N এর ভ্যালু ১০০০ হলে কাজটি কম বেশি
1000
∼৩১ বার সম্পাদন হয় সেই ক্ষেত্রে আমরা বলতে পারি, আমাদের কোডটির টাইম কমপ্লেক্সিটি O( N
)। খেয়াল করে দেখবেন, এইক্ষেত্রে আমাদের কোডের টাইম কমপ্লেক্সিটি অ্যানালাইসিস পদ্ধতি আগের মডিউলের টাইম কমপ্লেক্সিটি O(N) এর সাথে কিছু টা মিল রয়েছে। চলুন, কিছু কোডের উদাহরণ দেখে বিষয়টি আরো ভালোভাবে বোঝার চেষ্টা করি।
🔹 Problem 1:
int n; cin >> n;
for(int i = 1; i <= sqrt(n); i++){ if(n % i == 0){ cout << i << " "; cout << n/i << " "; } }
// Input : 100
// Output : 100 50 25 12 6 3 ...
উপরোক্ত কোডটি হলো কোন একটি নাম্বারের গুণনীয়ক বের করার জন্য ব্যবহার করা হয়। এখানে দেখুন, আমরা মেইন লুপটি ১ থেকে শুরু করে ঐ নাম্বার N এর স্কয়ার রুট পর্যন্ত চেক করতেছি। তাহলে, এই লুপটি ইনপুট N=১০ এর জন্য
10
∼৩ বার, ইনপুট ১০০ এর জন্য
100
∼১০ বার এবং
1000
∼৩১ বার চলবে। যেহেতু এটি একটি ইনপুট N এর জন্য ম্যাক্সিমাম তার স্কয়ার রুট পর্যন্ত চলছে, তাই এই কোডের টাইম কমপ্লেক্সিটি হলো O( N
)।
🔹 Problem 2:
int i = 1, s = 1;
while(s < n){ s = s + i; i++; } আমরা কিছু উদাহরণের সাহায্যে দেখার চেষ্টা করব এই কোড এর ইম্পর্ট্যান্ট পার্ট টুকু অর্থাৎ লুপটি N এর বিভিন্ন ইনপুটের জন্য কীভাবে কাজ করছে।
Text s s+i
1 1 1+1 = 2 (১ বার)
2 1+1 1+1+2 = 4 (২ বার)
3 1+1+2 1+1+2+3 = 7 (৩ বার)
4 1+1+2+3 1+1+2+3+4 = 11 > 10
এখানে দেখা যাচ্ছে N এর মান ১০ এর জন্য লুপটি ৩ বার চলবে। যা ১০ এর স্কয়ার রুট এর সমান অর্থাৎ
10
∼৩ এর সমান।
উপরে যদি আমরা লক্ষ্য করি s এর মান এর সাথে i এর মান শেষ পর্যন্ত কত যোগ করার পরে s এর মান N এর থেকে ছোট থাকতেছে ঠিক সেই পরিমাণ ই লুপ টি চলছে। আমরা ধরে নিই K ই হচ্ছে সবচেয়ে বড় সংখ্যা যা s এর সাথে যোগ হতে পারবে যাতে করে s এর মান N এর থেকে ছোট থাকে / সমান হয়।
1+1+2+3+⋯+K=N 1+ 2 K×(K+1) =N 2 K 2 +K =N [Constant এবং ছোট factor বাদ]
2 K 2
=N K 2 =N K= N
উপরে আমরা দেখছি, K এর মান ম্যাক্সিমাম হতে পারে স্কয়ার রুট N পর্যন্ত। এখন হয়তো মনে আসতে পারে, এই ছোট ফ্যাক্টর গুলা কি কোন ইফেক্ট ফেলবে না? এই লুপ টা আমরা চালালে N এর ভ্যালু ১০০ এর জন্য ১৪ বার চলবে যা exactly ১০০ এর বর্গমূল থেকে ৪ বেশি। সুতরাং এই হাতে গুনা কিছু ইটারেশন বেশি হলে ঐ বিষয়টি আমরা কমপ্লেক্সিটি তে include করি না। Overall ম্যাক্সিমাম স্কয়ার রুট N এর থেকে কিছু বেশি বা কম হতে পারে।
তাই উক্ত কোডের টাইম কমপ্লেক্সিটি হবে O( N
)।
🔹 সহজে মনে রাখার উপায়ঃ যখন আমাদের কোডে লুপের কন্ডিশন ০/১ থেকে শুরু হয়ে স্কয়ার রুট N পর্যন্ত চলে অথবা আমাদের আমাদের লুপের কন্ডিশন এর ভ্যারিয়েবল এমন ভাবে বাড়তে থাকে যে তা ১ থেকে শুরু করে কোন একটি নির্দিষ্ট স্বাভাবিক সংখ্যার যোগফল আকারে বাড়তে থাকে তবে এই ক্ষেত্রে আমরা বলতে পারি এই কোডের টাইম কমপ্লেক্সিটি হলো O( N
)। বেশি বেশি কোড দেখতে দেখতে এই টাইম কমপ্লেক্সিটি কীভাবে বের করতে হবে তা আমরা জানতে পারবো।
🌟 টাইম কমপ্লেক্সিটির কিছু উদাহরণ: 🔹 উদাহরণ ১:
for(int i=0; i<N; i++) // একটি লুপ চলছে ০ থেকে N পর্যন্ত -> কমপ্লেক্সিটি O(N)
{
x++;
}
for(int i=0; i<M; i++) // একটি লুপ চলছে ০ থেকে M পর্যন্ত -> কমপ্লেক্সিটি O(M) { y++; }
// টোটাল কমপ্লেক্সিটি O(N) + O(M) [ কারন দুটি লুপ আলাদাভাবে চলছে ] 🔹 উদাহরণ ২:
int a=0;
for(int i=0; i<N; i++) // একটি লুপ চলছে ০ থেকে N পর্যন্ত -> কমপ্লেক্সিটি O(N) { for(int j=N; j>i; j--) // একটি লুপ চলছে N থেকে i পর্যন্ত -> কমপ্লেক্সিটি O(N) [ worst কেসে j যখন ০ হয়ে যাবে তখন লুপটি পুরো N থেকে চলবে ] { a = a+i+j; } }
// টোটাল কমপ্লেক্সিটি O(N) * O(N) = O(N*N) [ কারন একটি লুপ আরেকটি লুপের ভিতরে আছে নেস্টেড আকারে ] 🌟 Space Complexity: টাইম কমপ্লেক্সিটিতে আমরা যেমন মেজার করেছি আমাদের কোড রান হতে কতগুলো অপারেশন চালায় বা কত বার লুপ চলে, ঠিক তেমনি Space Complexity (স্পেস কমপ্লেক্সিটি) হচ্ছে আমাদের কোড রান হওয়ার সময় মেমরিতে বা RAM এ কতটুকু অতিরিক্ত জায়গা নিচ্ছে তার মেজারমেন্ট।
ইনপুটের প্রেক্ষিতে আমাদের কোড মেমরিতে কতটুকু জায়গা দখল করছে তার হিসাবকেই আমরা স্পেস কমপ্লেক্সিটি বলি। একেও আমরা Big O Notation দ্বারা প্রকাশ করি।
🔹 O(1) স্পেস কমপ্লেক্সিটি (Constant Space): যদি আমাদের প্রোগ্রামে ইনপুটের মান যতই বাড়ানো হোক না কেন, মেমরির জায়গা সবসময় নির্দিষ্ট বা ফিক্সড থাকে, তবে তাকে O(1) স্পেস কমপ্লেক্সিটি বলা হয়।
int n; cin >> n;
int sum = 0;
for(int i = 1; i <= n; i++) { sum += i; } cout << sum << endl; ব্যাখ্যা: এখানে ইনপুট n এর মান ১০ বা ১০ লক্ষ যাই হোক না কেন, মেমরিতে জায়গা কিন্তু ফিক্সড (শুধুমাত্র n, sum এবং i ভ্যারিয়েবলের জন্য জায়গা লাগছে)। ইনপুটের সাথে সাথে কোনো নতুন মেমরি বা অ্যারে তৈরি হচ্ছে না। তাই এর স্পেস কমপ্লেক্সিটি হলো O(1)।
🔹 O(N) স্পেস কমপ্লেক্সিটি (Linear Space): ইনপুটের সাইজ বাড়ার সাথে সাথে আমাদের প্রোগ্রামের মেমরির জায়গাও যদি সমান হারে বাড়তে থাকে, তবে তাকে O(N) স্পেস কমপ্লেক্সিটি বলে।
int n; cin >> n;
int a[n]; // N সাইজের অ্যারে ডিক্লেয়ার করা হলো
for(int i = 0; i < n; i++) { cin >> a[i]; } ব্যাখ্যা: এখানে n এর মান যদি ১০ হয়, মেমরিতে ১০টি ঘরের অ্যারে তৈরি হবে। n এর মান ১০ লক্ষ হলে ১০ লক্ষ ঘরের অ্যারে তৈরি হবে। অর্থাৎ ইনপুট বাড়ার সাথে সাথে লিনিয়ারলি মেমরির জায়গাও বাড়ছে। তাই এর স্পেস কমপ্লেক্সিটি হলো O(N)।