Big O Notation পার্ট-১
আজকের ব্লগে আমরা Big 0 Notation সম্পর্কে জানব।আমরা যারা ইউনিভার্সিটির ছাত্র অথবা কোনো একসময় ছাত্র ছিলাম তারা Algorithm/Data Structure কোর্সের শুরুর দিকে Big O এর সম্পর্কে জেনেছিলাম । তো যারা আজও জিনিশগুলো ঠিক মত বুঝি নাই । আজকে আমরা চেস্টা করব কিছুটা বোঝার।
Big 0 কী ?
তো প্রথমেই আমরা Big 0 এর Formal Definition টি জেনে নেই…
Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

কিছু বোঝা গেল?? অনেকেই হয়ত বুঝবেন না … কিন্তু হতাশ হওয়ার কারন খুব একটা নেই । আমরা এই ব্লগে ও সামনে Big O এর ব্যাপারে বিস্তারিত আলোচনা করব।
একটি Algorithm এর পারফর্মেন্স বর্ণনা করতে Big O ব্যবহার করা হয়। পারফর্মেন্স বলতে Algorithm টি কতটুকু Scalable তা বোঝানো হয়।অর্থাৎ ধরে নিন আপনি একটি কোড লিখলেন যার ইনপুট ডাটা সেট খুবই ছোট ।তো আপনার মেশিনে এটি খুব দ্রুতই রান করল এবং Output দেখিয়ে দিল। কিন্তু যখন ইনপুট ডাটা সেট বড় হবে তখন আপনার কোড কেমন সময় নিবে Output দিতে/Algorithm টির পারফর্মেন্স কেমন হবে তা বর্ণনা করতে Big O ব্যবহার করা হয়।আর এই আউটপুট দেয়ার সময় / পারফরমেন্সের বিষয়টিকে Run Time Complexity বলা হয়।
ধরা যাক আপনি একটি সমস্যা সমাধানের জন্য দুইটি Algorithm বের করলেন এখন কোন Algorithm টি Efficient হবে অধিক ইনপুটের ক্ষেত্রে তা নির্ণয় এর জন্য Big O Analysis করা যেতে পারে।
তো আজকের ব্লগে আমরা Constant growth O(1) ও linear growth O(n) নিয়ে আলোচনা করব।
O(1)
উপরের কোডটুকু লক্ষ্য করুন , log মেথডটি একটি Integer টাইপের অ্যারে গ্রহন করে এবং কেবলমাত্র অ্যারের প্রথম এলিমেন্টটাকে প্রিন্ট করে। এখানে আমাদের অ্যারেতে এলিমেন্ট ১ টি হোক কিংবা ১ কোটি হোক তা ব্যাপার না । কারণ একটি Specific সিঙ্গেল অপারেশন এই মেথডটি চালাচ্ছে এবং অ্যারের প্রথম এলিমেন্টটাকে প্রিন্ট করছে । এবং অব্যশই তা একটি Constant Time নিচ্ছে।তাহলে আমরা মেথডটিকে O(1) দ্বারা বর্ণনা করতে পারি।এই O(1) এই মেথডটির Run Time Complexity। তো এই মেথডটির ক্ষেত্রে ইনপুট সাইজ কোনো ব্যাপার না এবং এটি একটি Constant Time নিবে।তাই এই মেথডটির Run Time Complexity হল O(1)।
এই কোডটুকু লক্ষ্য করলে দেখতে পাবেন । আমরা আগের প্রথম এলিমেন্টটাকে প্রিন্ট করার অপারেশনকে ২ বার চালিয়েছি। তাহলে এখন আমাদের Run Time Complexity কত হওয়া উচিত? O(1) + O(1) =O(2) ?? না যখন আমরা Run Time Complexity নিয়ে কাজ করব তখন কয়টা অপারেশান তা আমাদের বিবেচ্য বিষয় না। আমরা দেখব ইনপুট বাড়ার সাথে সাথে Algorithm টি কেমন আচরন করবে বা কতটুকু স্লো হবে । তাই আমাদের ইনপুট ডাটা যত বড় অথবা যত ছোটই হোক না কেন আমাদের এই অপারেশনটি চলতে একটি Constant Time ই লাগবে তাই আমরা এখানেও বলতে পারি Run Time Complexity হল O(1)।
O(n)
উপরের কোডটুকু লক্ষ্য করুন ,এখানে আমরা একটি অ্যারের সবগুলো এলিমেন্টকে প্রিন্ট করছি।যদি অ্যারেটিতে একটি এলিমেন্ট থাকে তবে একবারই প্রিন্ট অপারেশনটি চলবে অন্যথায় যত গুলো এলিমেন্ট থাকবে ঠিক ততবারি প্রিন্ট কাজ করবে।অর্থাৎ log মেথডটির আউটপুট সরাসরি অ্যারেতে থাকা এলিমেন্ট সংখ্যার উপর নির্ভরশীল । তাই আমরা বলতে পারি এই মেথডটির Run time complexity হল O(n) । যেখানে n হল অ্যারের টোটাল এলিমেন্ট সংখ্যা । তো আমরা বলতে পারি এই Algorithm এর cost linearly গ্রো করবে ইনপুট সংখ্যা বাড়ার সাথে সাথে ।
উপরের কোডটুকু লক্ষ্য করুন , আমরা আরও দুটি প্রিন্ট মেথড ফর লুপের উপরে এবং নিচে বসিয়েছি । ধরে নেই দুটি প্রিন্ট মেথডের জন্য আমাদের Run time complexity হল O(1) করে । তাহলে Run time complexity হছে O(1+n+1) = O(2+n) ।কিন্তু আসলে তা হবে O(n)। কারন ধরে নিই আমাদের অ্যারেতে ইনপুট এলিমেন্টের সংখ্যা ১ মিলিয়ন এই বিশাল ইনপুট প্রিন্ট করার আগে ও পরে মাত্র দুটি প্রিন্ট মেথড আমাদের Algorithm এর পারফরমেন্সকে খুব বেশি পরিবর্তন করতে পারবে নাহ।
উপরের কোডটুকু লক্ষ্য করুন ,আমরা এখানে দুইটি সেম ফর লুপ ব্যবহার করেছি ।তাহলে আমাদের এখন Run time complexity হবে O(n+n) = O(2n) ।কিন্তু না এখানেও আমাদের Run time complexity হবে O(n)। কারন Run time complexity তে আমাদের জানা দরকার Algorithm এর Approximate cost ইনপুট এর সাইজের সাপেক্ষে । O(n) বা O(2n) উভয়ই linearly গ্রোথকে Indicate করে ।তাই এখনেও Run time complexity হবেO(n)।
উপরের কোডটুকু লক্ষ্য করুন ,এখানে দুইটি ইনপুট Parameters ব্যবহার করা হয়েছে numbers এবং names সাথে দুইটি ফর লুপ ।তো ধরে নিই দুইটি ফর লুপ এর Run time cost যথাক্রমে O(n) এনং O(m) তাহলে এখন Run time complexity হবে O(n+m)। কিন্তু এখানেও আমরা Simplify করে বলতে পারি Run time complexity হবে O(n)।কারন O(n+m) linearly গ্রোথকে Indicate করে এবং O(n) ও O(n+m) ও linearly গ্রোথকে Indicate করে।
আজ এই পর্যন্তই ।পার্ট-২ তে আমরা দেখব O(n²) ,O(log n) সম্পর্কে।ততক্ষণ পর্যন্ত আল্লাহ হাফেজ।

