ডেটা স্ট্রাকচারে সময় এবং স্থানের জটিলতা

অ্যালগরিদম বিশ্লেষণ

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

একটি অগ্রাধিকার বিশ্লেষণ - এটি একটি অ্যালগরিদমের তাত্ত্বিক বিশ্লেষণ হিসাবে সংজ্ঞায়িত করা হয়। অ্যালগরিদমের কার্যকারিতা পরিমাপ করা হয় অনুমান করে যে অন্যান্য সমস্ত কারণ যেমন প্রসেসরের গতি, ধ্রুবক এবং বাস্তবায়নে কোন প্রভাব নেই।

একটি পোস্টেরিয়র বিশ্লেষণ - এটি একটি অ্যালগরিদমের অভিজ্ঞতামূলক বিশ্লেষণ হিসাবে সংজ্ঞায়িত করা হয়। নির্বাচিত অ্যালগরিদম প্রোগ্রামিং ভাষা ব্যবহার করে প্রয়োগ করা হয়। পরবর্তীতে নির্বাচিত অ্যালগরিদমটি লক্ষ্য কম্পিউটার মেশিনে কার্যকর করা হয়। এই বিশ্লেষণে, প্রকৃত পরিসংখ্যান যেমন চলমান সময় এবং স্থান প্রয়োজন।

অ্যালগরিদম বিশ্লেষণ জড়িত বিভিন্ন ক্রিয়াকলাপ সম্পাদন বা চলমান সময়ের সাথে মোকাবিলা করা হয়। একটি অপারেশন চলাকালীন সময়কে অপারেশন প্রতি নির্বাহিত কম্পিউটার নির্দেশাবলীর সংখ্যা হিসাবে সংজ্ঞায়িত করা যেতে পারে।

অ্যালগরিদম জটিলতা

ধরুন 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 পদক্ষেপ নেওয়া হয়। ফলস্বরূপ, মোট গণনামূলক সময় হল t(N) =c*n, যেখানে c হল দুটি বিট যোগ করার জন্য ব্যবহৃত সময়। এখানে, আমরা লক্ষ্য করি যে ইনপুট আকার বৃদ্ধির সাথে সাথে t(N) রৈখিকভাবে বৃদ্ধি পায়।