অ্যাসিম্পটোটিক কমপ্লেক্সিটি

অ্যাসিম্পটোটিক অ্যানালিসিস

অ্যাসিম্পটোটিক অ্যানালিসিস ব্যবহার করে আমরা ইনপুট সাইজের উপর ভিত্তি করে অ্যালগরিদমের পারফরম্যানস সম্পর্কে ধারণা পাই। আমাদের এক্সাক্ট রানিং টাইম ক্যালকুলেট করতে হবে না, বরং রানিং টাইম এবং ইনপুট সাইজের মধ্যে সম্পর্ক বের করতে হবে। ইনপুট সাইজ বাড়লে রানিং টাইম কীভাবে বদলা যাচ্ছে তা অনুসরণ করতে হবে।

স্পেস কমপ্লেক্সিটির জন্য, আমাদের লক্ষ্য হলো সম্পর্ক বা ফাংশন বের করা যে কত স্পেস মেইন মেমোরিতে দখল করে অ্যালগরিদম সম্পূর্ণ করতে।

অ্যাসিম্পটোটিক বিহ্যাভিওর

একটি ফাংশন f(n)-র জন্য অ্যাসিম্পটোটিক বিহ্যাভিওর হলো n বড় হলে f(n)-র বৃদ্ধি। ছোট ইনপুট মান বিবেচনা করা হয় না। আমাদের কাজ হলো বড় ইনপুটের জন্য কত সময় লাগবে তা বের করা।

উদাহরণস্বরূপ, f(n) = c * n + k হলো লিনিয়ার টাইম কমপ্লেক্সিটি। f(n) = c * n² + k হলো কোয়াড্রাটিক টাইম কমপ্লেক্সিটি।

অ্যালগরিদমের অ্যানালিসিস তিনটি ভিন্ন কেসে ভাগ করা যায়। কেসগুলো হলো −

বেস্ট কেস − এখানে রানিং টাইমের লোয়ার বাউন্ড ক্যালকুলেট করা হয়। এটি অপ্টিমাল কন্ডিশনে অ্যালগরিদমের আচরণ বর্ণনা করে।

এভারেজ কেস − এই কেসে রানিং টাইমের আপার এবং লোয়ার বাউন্ডের মধ্যে إقলিম ক্যালকুলেট করা হয়। এখানে এক্সিকিউটেড অপারেশনের সংখ্যা ন্যূনতম নয় এবং নয় সর্বাধিক।

ওয়ার্স্ট কেস − এই কেসে রানিং টাইমের আপার বাউন্ড ক্যালকুলেট করা হয়। এখানে সর্বাধিক সংখ্যক অপারেশন এক্সিকিউট হয়।