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

প্রবলেম সলভ এর এক একটি পদ্ধতি হলো এক একটি অ্যালগোরিদম। এখন কথা হচ্ছে একটি প্রব্লেম অনেক উপায়ে সল্ভ করা যায়।  অর্থাৎ অ্যালগোরিদম ও অনেক থাকতে পারে , সেক্ষেত্রে যে অ্যালগোরদমটি বেশী কার্যকরী সেটি ই বেছে নিব। কোন অ্যালগোরিদম ভালো তা বোঝার জন্য দেখতে হবে -আমি যে অ্যাালগোরিদম টি করব সেটি বড় ইনপুট এর জন্য কাজ করবে কিনা , আউটপুট পেতে কত সময় লাগবে , মেমোরি কতটুকু ব্যবহা্র  হচ্ছে । অ্যালগোরিদম এর কমপ্লেজিটি বের করে এই প্রশ্ন গুলোর উত্ত্রর পাওয়া যাবে।কমপ্লেজিটি বলতে মুলত  অ্যালগোরিদমের ধাপ এর উপর ভিত্তি করে বের করা হয়।  যেমনঃ

উপরের কোডটিতে n এর মান যাই হোক না কেন একটি মাত্র  constant ধাপ এর পর অ্যালগরদমটি কাজ করা শেষ করবে । তাই এর কমপ্লেজিটি O(1)।   BIG “O” নোটেশন হলো কমপ্লেক্সিটি লিখে প্রকাশ করার নোটেশন।

আবার এক্ষেত্রে কোডটিতে একটি লুপ আছে । লুপটি কত ধাপ চলবে তা n এর মানের উপর নির্ভর করে । n=5 হলে এটি পাঁচটি ধাপে চলবে বা n=10 হলে দশটি ধাপে চলবে । যেহেতু n এর মানের উপর নির্ভর করছে তাই এর কমপ্লেজিটি O(n)

লিনিয়ার সার্চঃ

লিনিয়ার সার্চ এর ক্ষেত্রে for লুপ দিয়ে সংখ্যা মান সার্চ করছি । যদি লিস্ট এর প্রথমেই সংখ্যাটি থাকে তখন লুপটি মাত্র এক বা্র চলবে। সেক্ষেত্রে এটি হবে best case. আর যদি সংখ্যাটি  লিস্ট এর সর্বশেষে থাকে বা লিস্টে না থাকে তখন লুপটি n সংখ্যকবার চলবে (worst case )। কমপ্লেজিটি এর ক্ষেত্রে প্রোগ্রামাররা সব সময় worst case নিয়ে কাজ করে। সুতরাং লিনিয়ার সার্চ এর কমপ্লেজিটি O(n).

বাইনা্রি সার্চঃ

  বাইনা্রি সার্চ এর ক্ষেত্রে প্রতিবার লিস্টকে দুইভাগে ভাগ করে , এর এক অংশ বা্দ দিয়ে দেই । এভাবে সার্চকৃত সংখ্যা না পাওয়া পর্যন্ত চলতে থাকে । এখন একটি সংখ্যাকে সর্বোচ্চ কত বার দুই দিয়ে ভাগ করা যায় যতক্ষন না পর্যন্ত ১ না হয় ? দেখা যাক ...

অর্থাৎ বাইনারি সার্চে সর্বোচ্চ log2(n) সংখ্যক ধাপের পর আমরা দরকারি সংখ্যাটা খুজে পাবো, সুতরাং এর কমপ্লেজিটি  O(log2(n))