মূলঃ Big O Notation Explained with Examples

প্রদত্ত কোন অ্যালগরিদম এর কমপ্লেক্সিটি বা অ্যালগোরিদমটি কত দ্রুত কাজ করে তা প্রকাশ করার একটি উপায় হল বিগ ও নোটেশন (Big O Notation)। আপনার বর্তমান প্রজেক্টটি যদি কোন পূর্বনির্ধারিত অ্যালগরিদম ব্যবহার করে, তাহলে সেই অ্যাগোরিদমটি অন্যান্য অপশনগুলি থেকে কতটুকু ফাস্ট বা স্লো তা বুঝা অত্যন্ত গুরুত্বপূর্ণ।

বিগ ও নোটেশন কি এবং এটি কিভাবে কাজ করে?

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

কিন্তু একটি অ্যালগোরিদম কত সেকেন্ডে একটি কাজ সম্পন্ন করবে, বিগ ও নোটেশন তা বলতে পারে না। অ্যালগোরিদম কাজ সম্পন্ন করতে কত সময় নিবে তা অনেকগুলি বিষয়ের উপরে নির্ভর করে। তাই, প্রদত্ত কোন অ্যালগোরিদমের অপারেশনের সংখ্যার ভিত্তিতে বিগ ও নোটেশন ব্যবহার করে অ্যালগোরিদমগুলি তূলণা করা হয়।

বিগ ও একটি worst-case রানটাইম স্থাপন করে

মনে করুন আপনি একজন শিক্ষক এবং আপনার একজন শিক্ষার্থীর নাম Jane। আপনি এই শীক্ষার্থীর রেকর্ড খুঁজে বের করার জন্য, আপনার স্কুলের ডেটাবেজে একটি সিম্পল সার্চ অ্যালগোরিদম চালালেন।

আপনি জানেন যে এধরণের সিম্পল সার্চ গুলো কাজ করার জন্য O(n) সংখ্যক সময় নেয়। তার মানে, worst-case এ Jane এর রেকর্ড খুঁজে পেতে আপনাকে প্রতিটি রেকর্ড (এখানে n দ্বারা প্রকাশ করা হয়েছে) দেখতে হবে।

কিন্তু সিম্পল সার্চটি চালানোর পরে আপনি দেখলেন যে Jane এর রেকর্ডটি ডেটাবেজের একদম শুরুতে আছে। আপনাকে সবগুলি রেকর্ড ঘেঁটে দেখতে হচ্ছে না, আপনি প্রথম চেষ্টাতেই আপনার কাঙ্ক্ষিত রেকর্ডটি পেয়েছেন।

তাহলে এই এলগোরিদম কি O(n) সংখ্যক সময় নিল? নাকি O(1) সংখ্যক সময় নিল, যেহেতু আপনি Jane এর রেকর্ডটি প্রথম চেষ্টাতেই পেয়ে গেলেন?

এই ক্ষেত্রে, O(1) হল best-case সিনারিও, আপনি ভাগ্যবান ছিলেন যে Jane এর রেকর্ডটি সবার উপরে ছিল। কিন্তু বিগ ও নোটেশন worst-case সিনারিওকে গুরুত্ব দেয় যা সিম্পল সার্চের ক্ষেত্রে O(n) হয়। আমাদের ভরসা এই যে সিম্পল সার্চ কখনোই O(n) সময়ের থেকে ধীর গতির হবে না।

অ্যালগোরিদমের রানিং টাইম বিভিন্ন হারে বৃদ্ধি পায়

মনে করুন সম্পূর্ণ স্কুলের ডেটাবেজের প্রত্যেকটি এলিমেন্ট দেখতে ১ মিলিসেকেন্ড সময় লাগে।

সিম্পল সার্চের মাধ্যমে আপনার যদি ১০টি এন্ট্রি দেখতে হয় তাহলে সময় লাগবে ১০ মিলিসেকেন্ড। কিন্তু, বাইনারি সার্চ অ্যালগোরিদম ব্যবহার করলে, আপনাকে শুধু ৩টি এলিমেন্ট দেখতে হবে, যার ফলে সময় লাগবে ৩ মিলিসেকেন্ড।

বেশির ভাগ ক্ষেত্রেই যেসব লিস্ট বা ডেটাবেজে আপনার সার্চ করতে হবে, সেগুলিতে শত শত বা হাজার হাজার এলিমেন্ট থাকবে।

যদি ডেটাবেজে ১ বিলিয়ন এলিমেন্ট থাকে তাহলে সিম্পল সার্চ চালাতে সময় লাগবে ১ বিলিয়ন মিলিসেকেন্ড বা ১১ দিন। অন্য দিকে, বাইনারি সার্চ ব্যবহার করলে, worst-case সিনারিওতেও মাত্র ৩২ মিলিসেকেন্ড সময় লাগবে।

31781165-723a053c-b500-11e7-937c-7b33db281efe

পরিষ্কার ভাবে বুঝা যাচ্ছে যে সিম্পল সার্চ এবং বাইনারি সার্চের রান টাইমগুলি একই হারে বৃদ্ধি পায় না। লিস্টে এন্ট্রির সংখ্যা যত বাড়তে থাকে, বাইনারি সার্চের চলার জন্য শুধু একটুখানি সময় বেশি দরকার পরে। কিন্তু লিস্টে এন্ট্রির সংখ্যা বাড়ার সাথে সাথে, সিম্পল সার্চের রান টাইম দ্রুতগতিতে বৃদ্ধি পেতে থাকে।

এজন্যই লিস্টের আকারের সাথে রানিং টাইম কিভাবে বৃদ্ধি পায় তা জানা অত্যন্ত জরুরি। এবং এজন্যই বিগ ও নোটেশন অত্যন্ত কাজের।

বিগ ও নোটেশন অপারেশনের সংখ্যা প্রকাশ করে

উপরে যেমনটা বলা হয়েছে, একটি অ্যালগোরিদম কত সময় চলবে তা বিগ ও নোটেশন প্রকাশ করে না। এটি প্রকাশ করে অ্যালগোরিদমটি কতগুলি অপারেশন চালাবে। এটি আপনাকে বলে একটি অ্যালগোরিদমের রানিং টাইম কি হারে বৃদ্ধি পায় এবং অন্যান্য অ্যালগোরিদমগুলির সাথে প্রদত্ত অ্যালগোরিদমটিকে তূলণা করার সুযোগ দেয়।

31781175-768c208e-b500-11e7-9718-e632d1391e2d

এখানে কিছু সাধারণ অ্যালগোরিদম এবং তাদের রান টাইম বিগ ও নোটেশনে দেওয়া হলঃ

Big O notation Example algorithm
O(log n) Binary search
O(n) Simple search
O(n * log n) Quicksort
O(n2) Selection sort
O(n!) Traveling salesperson

ভয়ঙ্কর হয়ে ওঠার জন্য যতটুক জানা দরকার, বিগ ও নোটেশন সম্পর্কে আপনি এখন ঠিক ততটুকু জানেন। যান এবার অ্যালগোরিদমগুলি তুলনা করা শুরু করে দিন।