ডেটা স্ট্রাকচারে টাইম এবং স্পেস কমপ্লেক্সিটি

অ্যালগরিদম অ্যানালিসিস

একটি অ্যালগরিদমের দক্ষতার বিশ্লেষণ দুটি ভিন্ন ধাপে করা যায়, বাস্তবায়নের আগে এবং পরে, যथा-

এPriori অ্যানালিসিস − এটি হলো একটি অ্যালগরিদমের সিদ্ধান্তিক বিশ্লেষণ। অ্যালগরিদমের দক্ষতা মাপা হয় ধরে নিয়ে যে অন্যান্য সব ফ্যাক্টর যেমন প্রসেসরের গতি, কনস্ট্যান্ট এবং বাস্তবায়নে কোনো প্রভাব ফেলে না।

এPosteriori অ্যানালিসিস − এটি হলো একটি অ্যালগরিদমের অভিজ্ঞতামূলক বিশ্লেষণ। নির্বাচিত অ্যালগরিদম প্রোগ্রামিং ল্যাঙ্গুয়েজ ব্যবহার করে বাস্তবায়ন করা হয়। এরপর নির্বাচিত অ্যালগরিদম টার্গেট কম্পিউটার মেশিনে এক্সিকিউট করা হয়। এই বিশ্লেষণে, এক্সিকিউশন টাইম এবং দরকার স্পেসের আসল Статистиক সংগ্রহ করা হয়।

অ্যালগরিদম অ্যানালিসিস বিভিন্ন অপারেশনের এক্সিকিউশন বা রানিং টাইমের সাথে কাজ করে। একটি অপারেশনের রানিং টাইম বলতে পারি প্রতি অপারেশনে এক্সিকিউট হওয়া কম্পিউটার ইনস্ট্রাকশনের সংখ্যা।

অ্যালগরিদম কমপ্লেক্সিটি

ধরা যাক X হলো একটি অ্যালগরিদম এবং N হলো ইনপুট ডেটার সাইজ, অ্যালগরিদম X দ্বারা ব্যবহৃত টাইম এবং স্পেস হলো X-এর দক্ষতা নির্ধারণকারী দুটি প্রধান ফ্যাক্টর।

টাইম ফ্যাক্টর − টাইম গণনা বা মাপা হয় কী অপারেশনের সংখ্যা গণনা করে যেমন সর্টিং অ্যালগরिदমে কমপেরিজন।

স্পেস ফ্যাক্টর − স্পেস গণনা বা মাপা হয় অ্যালগরিদম দ্বারা প্রয়োজনীয় সর্বোচ্চ মেমরি স্পেস গণনা করে।

একটি অ্যালগরিদমের কমপ্লেক্সিটি f(N) অ্যালগরিদমের রানিং টাইম এবং/অথবা স্টোরেজ স্পেস প্রদান করে N-র সাপেক্ষে ইনপুট ডেটার সাইজ হিসেবে।

স্পেস কমপ্লেক্সিটি

একটি অ্যালগরিদমের স্পেস কমপ্লেক্সিটি তার জীবনচক্রে অ্যালগরিদমের প্রয়োজনীয় মেমরি স্পেসের পরিমাণ প্রতিনিধিত্ব করে।

একটি অ্যালগরিদমের প্রয়োজনীয় স্পেস নিচের দুটি কম্পোনেন্টের যোগফলের সমান:

একটি ফিক্সড পার্ট যা কিছু ডেটা এবং ভেরিয়েবল স্টোর করার জন্য প্রয়োজনীয় স্পেস (যেমন সিম্পল ভেরিয়েবল এবং কনস্ট্যান্ট, প্রোগ্রাম সাইজ ইত্যাদি), যা সমস্যার সাইজের ওপর নির্ভরশীল নয়।

একটি ভেরিয়েবল পার্ট হলো ভেরিয়েবলগুলোর দ্বারা প্রয়োজনীয় স্পেস, যাদের সাইজ সম্পূর্ণরূপে সমস্যার সাইজের ওপর নির্ভরশীল। উদাহরণস্বরূপ, রিকার্শন স্ট্যাক স্পেস, ডাইনামিক মেমরি অ্যালোকেশন ইত্যাদি।

কোনো অ্যালগরিদম p-এর স্পেস কমপ্লেক্সিটি S(p) হলো S(p) = A + Sp(I) যেখানে A হলো ফিক্সড পার্ট এবং S(I) হলো অ্যালগরিদমের ভেরিয়েবল পার্ট যা ইন্সট্যান্স ক্যারেক্টারিস্টিক I-র ওপর নির্ভরশীল। নিচে একটি সিম্পল উদাহরণ দেওয়া হলো যা কনসেপ্টটি বোঝানোর চেষ্টা করে:

অ্যালগরিদম

SUM(P, Q) Step 1 - START Step 2 - R ← P + Q + 10 Step 3 - Stop

এখানে আমাদের তিনটি ভেরিয়েবল P, Q এবং R এবং একটি কনস্ট্যান্ট আছে। অতএব S(p) = 1+3। এখন স্পেস দেওয়া কনস্ট্যান্ট টাইপ এবং ভেরিয়েবলের ডেটা টাইপের ওপর নির্ভরশীল এবং সেগুলো অনুযায়ী গুণ হবে।

টাইম কমপ্লেক্সিটি

একটি অ্যালগরিদমের টাইম কমপ্লেক্সিটি হলো অ্যালগরিদমটি এক্সিকিউট হয়ে কমপ্লিট হওয়ার জন্য প্রয়োজনীয় টাইমের পরিমাণের রিপ্রেজেন্টেশন। টাইম রিকোয়ারমেন্ট একটি न्यूमেরিক্যাল ফাংশন t(N) হিসেবে ডেনোট বা সংজ্ঞায়িত করা যায়, যেখানে t(N) স্টেপ সংখ্যা হিসেবে মাপা যায়, প্রতিটি স্টেপ কনস্ট্যান্ট টাইম নেয় বলে ধরে।

উদাহরণস্বরূপ, দুইটি n-বিট ইন্টিজার যোগ করার ক্ষেত্রে, Nটি স্টেপ নেওয়া হয়। ফলে, মোট কম্পিউটেশনাল টাইম হলো t(N) = c*n, যেখানে c হলো দুইটি বিট যোগ করার জন্য খরচ হওয়া টাইম। এখানে, আমরা পর্যবেক্ষণ করি যে ইনপুট সাইজ বড়ার সাথে সাথে t(N) লিনিয়ারলি বৃদ্ধি পায়।