স্পেস কমপ্লেক্সিটি অ্যানালাইসিস
এই পাঠে যা শিখবেন
- অক্সিলিয়ারি স্পেস ও টোটাল স্পেসের সুনির্দিষ্ট পার্থক্য
- ইন-প্লেস অ্যালগরিদম কী, এবং কেন এটি প্রায়ই একটি কাম্য বৈশিষ্ট্য
sys.getsizeofদিয়ে সত্যিকারের মেমোরি পরিমাপ করা, এবং এর সীমাবদ্ধতা বোঝা- $O(1)$ বনাম $O(n)$ অক্সিলিয়ারি স্পেসের পার্থক্য একটি জেনুইন পরিমাপে প্রত্যক্ষ করা
১ · অক্সিলিয়ারি স্পেস বনাম টোটাল স্পেস
একটি অ্যালগরিদমের মোট মেমোরি ব্যবহার দুই ভাগে ভাগ করা যায়:
$$S_{\text{total}}(n) = S_{\text{input}}(n) + S_{\text{aux}}(n)$$
$S_{\text{input}}(n)$ হলো ইনপুট ডেটা স্টোর করতে যতটুকু মেমোরি লাগে (এটি সব অ্যালগরিদমেই সমান — ইনপুট নিজেই দিয়ে দেওয়া থাকে, অ্যালগরিদম এটি তৈরি করে না)। $S_{\text{aux}}(n)$ হলো অক্সিলিয়ারি স্পেস — অ্যালগরিদম চলাকালীন অতিরিক্ত যে মেমোরি ব্যবহার করে (টেম্পোরারি ভ্যারিয়েবল, নতুন ডেটা স্ট্রাকচার, রিকার্শন স্ট্যাক ইত্যাদি)। যেহেতু $S_{\text{input}}(n)$ প্রতিটি অ্যালগরিদমে একই থাকে, তাই তুলনা করার সময় সাধারণত আমরা শুধু $S_{\text{aux}}(n)$ নিয়েই কথা বলি — এটিই প্রকৃত পার্থক্য তৈরি করে।
ইনপুট ডেটা ধরে রাখতে যা লাগে — অ্যালগরিদম-নির্বিশেষে স্থির।
অ্যালগরিদম নিজে চালাতে যে অতিরিক্ত মেমোরি লাগে — এটিই সাধারণত তুলনার বিষয়।
$O(1)$ অক্সিলিয়ারি স্পেস ব্যবহার করে — ইনপুটকেই সরাসরি পরিবর্তন করে, নতুন কোনো বড় স্ট্রাকচার তৈরি করে না।
২ · কোড সেল — sys.getsizeof দিয়ে সত্যিকারের পরিমাপ
নিচের কোড সেলে দুটি রিভার্সাল ফাংশন আছে — একটি ইন-প্লেস (দুই-পয়েন্টার swap ব্যবহার করে, দেখুন
DSA কোর্স সাধারণ দুই-পয়েন্টার টেকনিকের বিস্তারিত জন্য), আরেকটি সম্পূর্ণ নতুন
একটি লিস্ট তৈরি করে। sys.getsizeof ব্যবহার করে অক্সিলিয়ারি স্ট্রাকচারের আকার পরিমাপ করা হয়েছে
ক্রমবর্ধমান $n$-এর জন্য।
import sys
def reverse_in_place(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
return arr # একই লিস্ট অবজেক্ট -- নতুন কোনো n-সাইজ স্ট্রাকচার তৈরি হয়নি
def reverse_new_list(arr):
reversed_list = []
for i in range(len(arr) - 1, -1, -1):
reversed_list.append(arr[i])
return reversed_list # সম্পূর্ণ নতুন একটি n-সাইজের লিস্ট
sizes = [100, 1_000, 10_000, 100_000]
print(f"{'n':>8} | {'in-place aux (bytes)':>22} | {'নতুন-লিস্ট aux (bytes)':>22} | {'অনুপাত':>10}")
for n in sizes:
original = list(range(n))
arr_copy = original.copy()
reverse_in_place(arr_copy)
left_var = 0
aux_inplace = sys.getsizeof(left_var) # শুধু একটি int ভ্যারিয়েবলের সাইজ -- n-নির্ভর নয়
new_list = reverse_new_list(original)
aux_new = sys.getsizeof(new_list) # পুরো নতুন লিস্ট অবজেক্টের সাইজ -- n বাড়লে বাড়ে
assert arr_copy == new_list == list(reversed(original)) # দুটোই সঠিক ফলাফল দেয় তা নিশ্চিত করা
print(f"{n:>8} | {aux_inplace:>22} | {aux_new:>22} | {aux_new / aux_inplace:>9.1f}x")
print("\nলক্ষ্য করুন: in-place কলামটি n বাড়লেও স্থির থাকে (O(1)),")
print("কিন্তু নতুন-লিস্ট কলামটি n-এর সাথে প্রায় সমানুপাতিকভাবে বাড়ে (O(n))।")sys.getsizeof একটি শ্যালো পরিমাপ — এটি শুধু
অবজেক্টটি নিজে কতটুকু মেমোরি নেয় তা বলে, তার ভেতরে থাকা রেফারেন্স করা অবজেক্টগুলোর (যেমন লিস্টের প্রতিটি
integer উপাদান) আকার যোগ করে না। তাছাড়া পাইথন সংস্করণ, প্ল্যাটফর্ম, ও ইন্টারপ্রেটার (CPython, Pyodide-এর
মতো ব্রাউজার-ভিত্তিক সংস্করণ) ভেদে প্রকৃত বাইট সংখ্যা কিছুটা ভিন্ন হতে পারে (যেমন সিপাইথনের লিস্ট
ওভার-অ্যালোকেশন করে, ফলে প্রকৃত সাইজ ঠিক $n$-এর সমানুপাতিক নাও হতে পারে ছোট পরিসরে)। তাই এই সংখ্যাগুলোকে
নিখুঁত বাইট-গণনা হিসেবে নয়, বরং প্রবণতা (in-place ধ্রুবক থাকে, নতুন-লিস্ট
$n$-এর সাথে বাড়ে) প্রদর্শনকারী একটি দৃষ্টান্ত হিসেবে দেখা উচিত — যা $O(1)$ বনাম $O(n)$ অক্সিলিয়ারি স্পেসের
তাত্ত্বিক দাবিরই একটি বাস্তব প্রতিফলন।
টাইম কমপ্লেক্সিটির মতোই, স্পেস কমপ্লেক্সিটিও অ্যালগরিদম বেছে নেওয়ার একটি গুরুত্বপূর্ণ মাপকাঠি — বিশেষত যখন ইনপুট এত বড় যে তা মেমোরিতে দুইবার রাখা অসম্ভব বা অব্যবহারিক (embedded ডিভাইস, স্ট্রিমিং ডেটা)। একটি $O(n\log n)$-সময়ের ইন-প্লেস অ্যালগরিদম কখনো কখনো একই টাইম কমপ্লেক্সিটির কিন্তু $O(n)$ অক্সিলিয়ারি স্পেস লাগা অ্যালগরিদমের চেয়ে ব্যবহারিকভাবে ভালো পছন্দ হতে পারে — L15-এর মার্জ সর্ট (যা $O(n)$ অক্সিলিয়ারি স্পেস লাগে) বনাম L16-এর কুইক সর্ট (যা ইন-প্লেস, $O(\log n)$ রিকার্শন-স্ট্যাক স্পেস লাগে) এই ট্রেড-অফের একটি ধ্রুপদী উদাহরণ।
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।
প্র ০১
উপরের কোডে aux_inplace পরিমাপ করতে sys.getsizeof(left_var) ব্যবহার করা
হয়েছে, যা একটি একক ইন্টিজারের সাইজ দেয়। কিন্তু ফাংশনে তো left এবং right — দুটো
ভ্যারিয়েবল আছে। এটি কি পরিমাপকে ভুল করে দেয়?
বড় ভুল নয় — কারণ এখানে মূল পয়েন্টটি হলো এই ভ্যারিয়েবলের সংখ্যা $n$-নির্বিশেষে স্থির
(হয় ১টি হোক বা ২টি, উভয়ই একটি ধ্রুবক, $n$ বাড়লে বাড়ে না)। তাই $O(1)$ দাবির জন্য গুরুত্বপূর্ণ বিষয় হলো
"$n$-নির্ভর নয়" এই ধর্মটি, ঠিক সংখ্যাটি ১ না ২ তা নয়। একটি আরও সম্পূর্ণ পরিমাপ হতো
sys.getsizeof(0) * 2, কিন্তু গ্রোথ-প্যাটার্নের সিদ্ধান্তে (স্থির বনাম n-এর সাথে বৃদ্ধি) কোনো
পার্থক্য আসত না।
প্র ০২
reverse_in_place ফাংশনটি নিজেই কি কোনো নতুন মেমোরি লিস্ট আকারে ব্যবহার করে, নাকি একেবারেই
না?
একেবারেই নতুন কোনো লিস্ট তৈরি হয় না — এটিই "ইন-প্লেস" শব্দের অর্থ। তবে টেকনিক্যালি, প্রতিটি
arr[left], arr[right] = arr[right], arr[left] লাইনে CPython অভ্যন্তরীণভাবে একটি ছোট
অস্থায়ী টাপল তৈরি করে সোয়াপ করার জন্য, কিন্তু এই টাপলের আকার $O(1)$ (শুধু দুটি রেফারেন্স ধরে রাখে,
$n$-নির্ভর নয়) এবং তা তাৎক্ষণিকভাবে বাতিল হয়ে যায়। তাই সামগ্রিক অক্সিলিয়ারি স্পেস দাবি $O(1)$ হিসেবেই
অক্ষুণ্ণ থাকে — এটি একটি ইমপ্লিমেন্টেশন ডিটেইল, অ্যালগরিদমিক দাবি নয়।
প্র ০৩ যদি একটি অ্যালগরিদমের টাইম কমপ্লেক্সিটি $O(n)$ কিন্তু স্পেস কমপ্লেক্সিটি $O(n^2)$ হয় (যেমন একটি সরল কিন্তু অপচয়ী মেমোয়াইজেশন টেবিল), তাহলে সেটিকে কি "ভালো" অ্যালগরিদম বলা যায়?
এটি নির্ভর করে প্রেক্ষাপটের উপর — এখানেই টাইম-স্পেস ট্রেড-অফের ধারণাটি গুরুত্বপূর্ণ হয়ে ওঠে। ছোট $n$-এর জন্য বা যথেষ্ট মেমোরি থাকা সিস্টেমে এটি সম্পূর্ণ গ্রহণযোগ্য হতে পারে। কিন্তু বড় $n$-এ ($n = 10^6$ হলে $n^2 = 10^{12}$) এই স্পেস চাহিদা ব্যবহারিকভাবে অসম্ভব হয়ে যাবে, এমনকি যদি টাইম কমপ্লেক্সিটি চমৎকার হয়। এই কারণেই একটি অ্যালগরিদমকে মূল্যায়ন করার সময় শুধু টাইম নয়, স্পেস কমপ্লেক্সিটিও সবসময় রিপোর্ট করা উচিত — M6-এর ডাইনামিক প্রোগ্রামিং অধ্যায়ে আমরা বারবার দেখব কীভাবে একটি $O(n^2)$-স্পেসের DP টেবিলকে "স্পেস-অপটিমাইজড" করে $O(n)$ বা এমনকি $O(1)$-এ নামিয়ে আনা যায়।
অনুশীলন
-
চিন্তা করুন: যদি
sizesলিস্টে1_000_000যোগ করা হয়, তাহলেaux_inplaceকলামের মান কী হবে বলে আপনার ধারণা?একই থাকবে — $n=100$-এ যা ছিল, $n=1{,}000{,}000$-এও ঠিক তাই থাকবে, কারণ
aux_inplaceশুধু একটি একক integer ভ্যারিয়েবলের সাইজ পরিমাপ করে, যা $n$-এর মানের উপর নির্ভর করে না। এটিই $O(1)$ অক্সিলিয়ারি স্পেসের প্রকৃত অর্থ — সম্পূর্ণ স্থির, ইনপুট সাইজ নির্বিশেষে। -
পরীক্ষা করুন: উপরের কোড সেলে
sizesলিস্টে1_000_000যোগ করে চালিয়ে দেখুন —aux_newকলামের মান কি $n$-এর সাথে মোটামুটি সমানুপাতিকভাবে বেড়েছে?হ্যাঁ —
aux_newপ্রতিবার $n$ প্রায় ১০ গুণ বাড়লে প্রায় ১০ গুণ বেড়ে যাবে (সিপাইথনের লিস্ট ওভার-অ্যালোকেশনের কারণে অনুপাতটি নিখুঁত ১০.০ নাও হতে পারে, কিন্তু প্রবণতা স্পষ্টভাবে রৈখিক থাকবে) — যেখানেaux_inplaceসম্পূর্ণ অপরিবর্তিত থাকবে। এই বৈসাদৃশ্যই $O(1)$ বনাম $O(n)$ অক্সিলিয়ারি স্পেসের মূল শিক্ষা।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- কোর্সের সম্পূর্ণ সিলেবাস দেখুন ৫৭টি পাঠ অ্যাসিম্পটোটিক অ্যানালাইসিস, রিকারেন্স, ডিভাইড অ্যান্ড কনকার, গ্রিডি, DP, গ্রাফ অ্যালগরিদম, ব্যাকট্র্যাকিং, স্ট্রিং অ্যালগরিদম, অ্যামর্টাইজড অ্যানালাইসিস, NP-কমপ্লিটনেস ও অ্যাপ্রক্সিমেশন — বাকি পাঠগুলো শীঘ্রই যুক্ত হবে।
- Data Structures & Algorithms কোর্স সহোদর কোর্স অ্যারে, লিস্ট ও অন্যান্য ডেটা স্ট্রাকচারের মেমোরি লেআউট বিস্তারিত সেই কোর্সে দেখুন।
- সব Courses দেখুন ABCL TECH C, C++, Python, Java, JavaScript, DSA, DBMS, Discrete Mathematics, System Design, Cybersecurity, Cloud Computing & DevOps, Computer Networks, Operating Systems, Computer Architecture, Programming Languages & Compiler Design, Software Engineering & Git, Theory of Computation, Engineering Economics, Full-Stack Web Frameworks, Mobile App Development, Ethics in Computing & AI Safety, Software Testing & Quality Assurance ও Design and Analysis of Algorithms — সব এক জায়গায়।