The space complexity of a recursive algorithm is mainly due to:
A
Input size
B
Output size
C
Variables inside loops
D
Function call
উত্তরের বিবরণ
একটি recursive algorithm-এ প্রতিবার ফাংশন নিজেকে কল করলে একটি নতুন ফাংশন কল স্ট্যাক ফ্রেমে যুক্ত হয়, যা অতিরিক্ত মেমরি ব্যবহার করে। এই কারণেই recursion-এর space complexity প্রধানত function call-এর সংখ্যা ও গভীরতার (depth) ওপর নির্ভর করে।
বিস্তারিতভাবে:
প্রতিটি function call স্ট্যাকে একটি নতুন stack frame তৈরি করে।
এই ফ্রেমে থাকে local variables, parameters, এবং return address, যেগুলোর জন্য নির্দিষ্ট পরিমাণ মেমরি বরাদ্দ হয়।
মোট ব্যবহৃত মেমরি recursion-এর সর্বাধিক গভীরতা (maximum recursion depth) অনুসারে বৃদ্ধি পায়।
ফলে recursive function-এর space complexity সরাসরি function calls-এর সংখ্যা ও স্তর দ্বারা নির্ধারিত হয়।
ভুল বিকল্পগুলো:
Input size: এটি মূলত time complexity-কে প্রভাবিত করে, stack space-কে নয়।
Output size: শুধুমাত্র তখনই space প্রভাবিত করে যদি ফলাফলগুলো স্পষ্টভাবে সংরক্ষণ করা হয়।
Variables inside loops: এগুলো একই stack frame-এ থাকে, তাই recursion-এর মতো অতিরিক্ত stack space ব্যবহার করে না।
অতএব, recursion-এ space complexity-এর প্রধান উৎস হলো function calls।
0
Updated: 2 days ago
Which optimization technique is not used for eliminating redundant codes?
Created: 2 days ago
A
Dead code elimination
B
Partial redundancy elimination
C
Common subexpression elimination
D
Constant folding
Constant folding হলো একটি code optimization technique, যা কম্পাইলার দ্বারা প্রোগ্রামের কার্যকারিতা বাড়ানোর জন্য ব্যবহৃত হয়। এটি মূলত স্থির মান (constant value) যুক্ত এক্সপ্রেশনগুলোকে কম্পাইল টাইমেই গণনা করে ফলাফল স্থাপন করে, ফলে রানটাইমে অপ্রয়োজনীয় গণনা এড়ানো যায়।
বিস্তারিতভাবে:
Constant Folding: এটি কম্পাইল টাইমে স্থির মানগুলোর ওপর গণনা সম্পন্ন করে, যেমন 3 + 5 → 8 এ রূপান্তরিত হয়।
এর মাধ্যমে প্রোগ্রাম দ্রুত চলে, কারণ এই গণনাগুলো রানটাইমে পুনরায় করতে হয় না।
এটি রিডানড্যান্ট কোড সরানোর উদ্দেশ্যে নয়, বরং কার্যক্ষমতা (efficiency) বৃদ্ধির উদ্দেশ্যে ব্যবহৃত হয়।
অন্য বিকল্পগুলোর বিশ্লেষণ:
(ক) Dead Code Elimination: কখনোই কার্যকর হয় না বা প্রোগ্রামের আউটপুটে প্রভাব ফেলে না এমন কোড সরিয়ে দেয়।
(খ) Partial Redundancy Elimination (PRE): এমন এক্সপ্রেশন সরায় যেগুলো কিছু নির্দিষ্ট পথে একাধিকবার গণনা হয়।
(গ) Common Subexpression Elimination (CSE): একাধিকবার পুনরাবৃত্ত এক্সপ্রেশন সনাক্ত করে এবং একবার গণনা করা ফল পুনরায় ব্যবহার করে।
(ঘ) Constant Folding: স্থির মানের গণনা আগে থেকেই সম্পন্ন করে, ফলে কোড আরও দ্রুত ও দক্ষভাবে চলে।
0
Updated: 2 days ago
The number of binary strings of length 5 is:
Created: 2 days ago
A
10
B
25
C
32
D
64
একটি binary string হলো এমন একটি স্ট্রিং যা কেবলমাত্র 0 এবং 1 দিয়ে গঠিত হয়। যদি স্ট্রিংটির দৈর্ঘ্য ৫ হয়, তবে প্রতিটি অবস্থানে দুইটি সম্ভাব্য মান থাকতে পারে—০ বা ১।
মূল তথ্যসমূহ:
প্রতিটি বিটে ২টি সম্ভাবনা থাকে: 0 বা 1।
মোট সম্ভাব্য স্ট্রিংয়ের সংখ্যা নির্ণয়ের সূত্র:
এখানে দৈর্ঘ্য = ৫, সুতরাং
অতএব, দৈর্ঘ্য ৫-এর একটি বাইনারি স্ট্রিংয়ের সম্ভাব্য মোট সংখ্যা ৩২, অর্থাৎ সঠিক উত্তর গ) 32।
0
Updated: 2 days ago
A page fault occurs when:
Created: 2 days ago
A
Deadlock happens
B
Page is found in memory
C
Page is found in memory
D
Page is not found in memory
Page fault হলো virtual memory management-এর একটি গুরুত্বপূর্ণ ধারণা, যা তখন ঘটে যখন কোনো প্রক্রিয়া এমন একটি page-এ প্রবেশ করতে চায় যা বর্তমানে RAM-এ উপস্থিত নয়। এই অবস্থায় অপারেটিং সিস্টেম সেই page-টি secondary storage (যেমন হার্ডডিস্ক) থেকে এনে main memory-তে লোড করে, যাতে প্রক্রিয়াটি কাজ চালিয়ে যেতে পারে।
বিস্তারিতভাবে:
Page: এটি একটি নির্দিষ্ট আকারের মেমরি ব্লক, যা paging প্রক্রিয়ায় ব্যবহৃত হয়।
যখন কোনো process একটি page অ্যাক্সেস করতে চায়, তখন—
যদি page RAM-এ থাকে, তবে স্বাভাবিকভাবে কাজ চলতে থাকে (কোনো সমস্যা হয় না)।
যদি page RAM-এ না থাকে, তখন page fault ঘটে এবং OS secondary storage থেকে সেই page আনে।
এই প্রক্রিয়ায় কিছুটা সময় লাগে, কারণ disk access RAM-এর তুলনায় অনেক ধীর।
একবার পৃষ্ঠা লোড হলে, প্রোগ্রামটি যেখানে থেমেছিল সেখান থেকেই পুনরায় কাজ শুরু করে।
ভুল বিকল্পগুলো:
(ক) Deadlock ঘটে → এটি process synchronization সম্পর্কিত, page fault নয়।
(খ) Segmentation শুরু হয় → এটি অন্য ধরনের memory management technique, paging নয়।
(গ) Page মেমরিতে পাওয়া যায় → এ ক্ষেত্রে কোনো page fault ঘটে না।
অতএব, page fault ঘটে তখনই, যখন প্রয়োজনীয় page RAM-এ উপস্থিত থাকে না।
0
Updated: 2 days ago
