TLE! TLE! TLE!
মানে time limit is exceeded । প্রবলেম সলভিং করতে গিয়ে এই সমস্যাটায় আমাদের অনেকেরই পরতে হয়েছে । Time limit is exceeded এই সমস্যাটা পার করার জন্যই আমাদের অ্যালগরিদমের Time complexity বুঝা দরকার ।
টাইম কমপ্লেক্সিটি বুঝাটা প্রোগ্রামিং এ for
লুপ ব্যবহার করতে শিখার মতোই গুরুত্বপূর্ন । টাইম কমপ্লেক্সিটি (Time complexity) এর সাথে 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 । এটাই আমাদের টাইম কমপ্লেক্সিটি (Time complexity)।
এখন যদি n = 1000 হয় তবে n2 = 106 খুব আরামে পার হয়ে যবে । কিন্তু যদি n = 106 হয় তবে এই কোড ১ ঘন্টাতেও শেষ হবে কিনা সন্দেহ আছে মানে নিশ্চিত Time limit is exceeded (TLE)। তাহলে n এর মান বেশি হলে n2 অ্যালগরিদমে TLE খাওয়া লাগবে । তাহলে আমরা কি এটাকে আরও optimize করতে পারি ? উত্তর হলো হ্যা । আমরা যদি উপরের সিরিজটার ভেতরে যে সিরিজ দেয়া আছে তা সূত্রের মাধ্যমে বের করি তবে আমাদের কমপ্লেক্সিটি O(n) এ নেমে আসবে । কিন্তু যদি এমন হয় n এর মানই 1012 তবে উপরের সূত্র দিয়ে করাটা বৃথা যাবে । এটার জন্য আরেকটা সূত্র ব্যবহার করতে হবে ।
সূতরাং দেখা যাচ্ছে এই সূত্রে দিয়ে বের করলে কোন লুপ লাগবে না । আমরা সাধারন কিছু হিসেব করেই করে ফেলতে পারি । তাই একে বলা হয় O(1) অ্যালগরিদম ।
অ্যালগোরিদমের কমপ্লেক্সিটি হলো ,এর মানে হলো ইনপুটের আকার যেমনই হোকনা কেন একটি constant টাইমে অ্যালগোরিদমটি কাজ করা শেষ করবে।
আরও পড়ার জন্য :
অ্যালগরিদম কমপ্লেক্সিটি(বিগ “O” নোটেশন)
সংখ্যাতত্ত্ব: মৌলিক সংখ্যা (prime number) ও তার অ্যালগরিদম
for further help, please comment down below. 🙂
R ai sutro gulo ber korte hoi kivabe? Kono rules ase? naki nije theke create korte hoi?
Next পোস্টে লিখবো ইনশাআল্লাহ্
খুব ভাল লিখেছ শরীফ ,,,,
শুভ কামনা রইল,,,,
ধন্যবাদ ভাই ❤️
Khub Valo ar Clear explanation Oshadharon ❤️ …
❣️