অ্যালগরিদমে টাইম কমপ্লিক্সিটি(complexity) - পর্ব (০২)

 

ডাটা-স্ট্রাকচার এন্ড অ্যালগরিদমে টাইম কমপ্লিক্সিটি একটি গুরুত্বপূর্ণ বিষয় তাই আমাদের এইটা সম্পর্কে খুব  ভালো ধারণা থাকতে হবে । গতপর্বে আমরা টাইম কমপ্লিক্সিটি সম্পর্কে বেশ কিছু জেনেছিলাম এবং শিখেছিলাম ।

এই পর্বে আমরা আরও টাইম কমপ্লিক্সিটি  সম্পর্কে জানবো । প্রথমেই একটি সহজ  প্রোগ্রাম দিয়ে শুরু করা যাক 

const printer = (n) => {
    for(let i = 0; i*i<=n; i++){
    console.log("shakil");
    }
}
printer(25);
  

আপনি কি বলতে পারবেন, উপরোক্ত প্রোগ্রামের টাইম কমপ্লিক্সিটি কত ? একটু লক্ষ্য করলে দেখবেন যে, এখানে i এর মান ১ করে বাড়তেছে কিন্তু কন্ডিশন i*i এইভাবে চেক করতেছে। তাহলে লুপটি কতবার চলবে আর shakil লিখাটি কতবার প্রিন্ট করবে ?

 

২৫ এর জন্য লুপটি ৫ বার ঘুরতেছে তাহলে shakil লিখাটি ৫ বার প্রিন্ট করবে । যদি প্যাঁরামিটার ৩৬ হয়তো তাহলে লুপটি ৬ বার চলতো অথবা প্যাঁরামিটার ৪৯ হয়তো লুপটি ৭ বার চলতো এবং লুপ অনুযায়ী shakil লিখাটি প্রিন্ট করতো ।

এখানে একটা জিনিস খেয়াল করুন আমরা প্যাঁরামিটার হিসেবে যাই পাস করি নাহ কেন তার রুট(root ) √ সংখ্যক বার লুপটি চলতেছে।


তাহলে এই প্রোগ্রামের টাইম কমপ্লিক্সিটি হইলো অর্ডার অব রুট এন O(√n)।

আচ্ছা এইবার আমি যদি প্যাঁরামিটারে ২০ পাঠাই তাহলে কতবার লুপটি চলবে ? একটু ভাবুন তো আশা করি আপনারা পেরেছেন। হ্যাঁ ৪ বার লুপটি চলবে -

 যখন i এর মান 1 তখন 1*1 = 1 যা 20 থেকে ছোট । এভাবে i এর মান 4 পর্যন্ত যাবে যা উপরোক্ত কন্ডিশনের সাথে ম্যাচ করে। তাহলে বলতে পারি যে, এই প্রোগ্রামের টাইম কমপ্লিক্সিটি অর্ডার অব রুট এন O(√n)।

এবার একটি নেস্টেড লুপসহ প্রোগ্রাম দেখা যাক।

 Writer is sleeping....