AlgorithmProblem Solving

Time complexity – বিগ O নোটেশন

TLE! TLE! TLE!

মানে time limit is exceeded । প্রবলেম সলভিং করতে গিয়ে এই সমস্যাটায় আমাদের অনেকেরই পরতে হয়েছে । এই সমস্যাটা পার করার জন্যই আমাদের অ্যালগরিদমের Time complexity বুঝা দরকার ।

Various time complexity
Algorithm time complexity

টাইম কমপ্লেক্সিটি বুঝাটা প্রোগ্রামিং এ for লুপ ব্যবহার করতে শিখার মতোই গুরুত্বপূর্ন । টাইম কমপ্লেক্সিটি এর সাথে Efficient and complex প্রোগ্রাম লেখতে পারার সম্পর্ক আছে । আসলে এটা জানতে আমরা বুঝতে পারবো কোন বিশেষ অবস্থায় কোন ধরনের অ্যালগরিদম সবচেয়ে ফলপ্রসূ হবে । সহজ কথায় বলতে গেলে একটি প্রোগ্রাম রান করতে কতখানি সময় নেয় তাকেই টাইম কমেপ্লেক্সিটি বলে ।আমরা একই সমস্যার একাধিক সমাধান এর জন্য টাইম কমপ্লেক্সিটি ব্যবহার করে থাকি । আশা করি এবার বিষয় টা আরও বেশি পরিষ্কার হবে ।

ধরা যাক একটা সিরিজ 1+(1+2)+(1+2+3)+..+(1+2+..+n) এখানে যদি আপনি for লুপ চালিয়ে হিসাব করেন তাহলে সর্বোমোট  (n2+n)/2  টা হিসাব করতে হবে । এখানে আমরা বুঝার স্বার্থে সবচেয়ে বড় টার্মটি বিবেচনা করি । এখানে n এর দুটি টার্ম আছে । একটি n এবং আরেকটি n2 এর টার্ম । n এর টার্ম বাদ দিলে আমাদের থাকে n2/2 আমরা constant coefficient বাদ দিবো ।

কমপ্লেক্সিটি হিসাবের সময় constant factor গুলোকে বাদ দিয়ে দিতে হয়। তবে কোড লেখার সময় constant factor এর কথা অবশ্যই মাথায় রাখতে হবে।

worst case এ যতগুলো ইনস্ট্রাকশন থাকবে সেটাই আমাদের কমপ্লেক্সিটি।

সুতরাং আমরা যা পেলাম তা হলো n2 । এটাই আমাদের টাইম কমপ্লেক্সিটি ।

এখন যদি n = 1000 হয় তবে n2 = 106 খুব আরামে পার হয়ে যবে । কিন্তু যদি n = 106 হয় তবে এই কোড ১ ঘন্টাতেও শেষ হবে কিনা সন্দেহ আছে মানে নিশ্চিত time limit is exceeded। তাহলে n এর মান বেশি হলে n2 অ্যালগরিদমে TLE খাওয়া লাগবে । তাহলে আমরা কি এটাকে আরও optimize করতে পারি ? উত্তর হলো হ্যা । আমরা যদি উপরের সিরিজটার ভেতরে যে সিরিজ দেয়া আছে তা সূত্রের মাধ্যমে বের করি তবে আমাদের কমপ্লেক্সিটি O(n) এ নেমে আসবে । কিন্তু যদি এমন হয় n এর মানই 1012 তবে উপরের সূত্র দিয়ে করাটা বৃথা যাবে । এটার জন্য আরেকটা সূত্র ব্যবহার করতে হবে ।
1/2(n(n+1)(2n+1)/6+(n2+n)/2)

সূতরাং দেখা যাচ্ছে এই সূত্রে দিয়ে বের করলে কোন লুপ লাগবে না । আমরা সাধারন কিছু হিসেব করেই করে ফেলতে পারি । তাই একে বলা হয় O(1) অ্যালগরিদম ।

অ্যালগোরিদমের কমপ্লেক্সিটি হলো ,এর মানে হলো ইনপুটের আকার যেমনই হোকনা কেন একটি constant টাইমে অ্যালগোরিদমটি কাজ করা শেষ করবে।

আরও পড়ার জন্য :

অ্যালগরিদম কমপ্লেক্সিটি(বিগ “O” নোটেশন)

Wikipedia

for further help ,please comment down bellow . 🙂

Tags

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Close
Close