"Big O"-র সাথে কুস্তি: প্রথম পর্ব

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

সহজ ভাষায় বিগ ও হলো আপনার এলগোরিদম শুরু থেকে শেষ পর্যন্ত যতগুলো স্টেপ নিবে তার যোগফল। এখন আপনার যদি অনেক ভাব নিয়ে কারো সামনে বিগ ও-র ডেফিনেশন বলতে হয় তাহলে বলবেন-
"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" - Wikipedia

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

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

একটা উদাহরণ দিয়ে বোঝায়-
মনে করেন আপনি একটি প্রোগ্রাম লিখলেন একটি array র সকল এলিমেন্ট এর যোগফল বের করার জন্য।

def sum_of_array(arr):
    sum = 0
    for num in arr:
        sum += num

    return sum

একদম প্রথমে আমরা একটা ভ্যারিয়েবল ডিক্লেয়ার করেছি sum নামের। এই ভ্যারিয়েবল টি একটি স্টেপ। তাই এখানে বিগ ও হবে O(1) (আমরা বিগ ও র সিনটেক্স এইভাবে লিখি- একটি বড় হাতের O এবং তারপর ফার্স্ট ব্রাকেট এর ভিতর স্টেপ এর সংখ্যা।) ভ্যারিয়েবলটির পরে আমরা একটি লুপ চালাচ্ছি। এখন এই লুপ এর বিগ ও কেমন হবে? এরে টি তে যতগুলো এলিমেন্ট আছে লুপ টি ততবার চলবে এবং প্রত্যেকবার sum এ কারেন্ট নম্বর টি যোগ করবে তারমানে একটি স্টেপ। ধরে নিলাম এরে তে "n" সংখ্যক নম্বর আছে। তারমানে এখানে মোট স্টেপ এর সংখ্যা হবে- 1 * n = n। তাই আমরা বিগ ও তে "n" যোগ করে দিবো। তাহলে এখন বিগ ও হবে- O(1 + n)। এরপরে আমরা একটি রিটার্ন স্টেটমেন্ট দেখতে পাচ্ছি এই রিটার্ন স্টেটমেন্ট টি ১ টি স্টেপ। তাহোলে আমাদের ফাইনাল বিগ ও হবে-
O(1 + n + 1) = O(2 + n)

এখন ভাই কোনটাকে একটা স্টেপ ধরবো আর কোনটাকে এইরকম "n" স্টেপ ধরবো? যেখানে আপনার কোড ইনপুট এর সাইজও এর উপর নির্ভর করবে না সেটি ১ টি স্টেপ এবং নির্ভর করলে “n” বা “m” বা “a” বা “b” টি স্টেপ। (লক্ষ্য করেন এখানে “n” ধরতে হবে এমন কোনো কথা নেই. আপনি যেকোনো কিছু ধরতে পারেন কিন্তু “n” ধরা একটি বেস্ট প্রাকটিস।) উপরের কোড দিয়ে আপনাকে স্টেপ এর বিষয় টি আরেকটু ভালো করে বুঝিয়ে দি- দেখেন ফার্স্ট লাইন এ আমরা যেখানে sum ভ্যারিয়েবল টি লিখেছি সেখানে আমরা ইনপুট এরে টির সাইজ এর উপর নির্ভর করছি না। কারণ সাইজ যাই হোক আমরা sum ভ্যারিয়েবল টিতে 0 এসাইন করবো। তাই এখানে একটি স্টেপ। তারপরে ফর লুপ টি কিন্তু এরে র সাইজ এর উপর নির্ভর করে, কেননা আপনার এরে র সাইজ যদি হয় ৫ তাহলে ফর লুপ এর ভিতরের কোড চলবে ৫ বার, যদি সাইজ ১০ হয় তাহলে ফর লুপ এর ভিতরের কোড চলবে ১০ বার। তাই আমরা এখানে "n" স্টেপ নিয়েছি। শেষে আমরা sum ভ্যারিয়েবল টি রিটার্ন করছি। আপনার এরে র সাইজ যতই হোক না কেন আমরা কিন্তু sum ভ্যারিয়েবল টি রিটার্ন করবো তারমানে এখানে আমরা একটি স্টেপ নিচ্ছি।

আপনি যদি এই পর্যন্ত বুঝে থাকেন তাহলে আপনি বিগ ও র বেসিকটুকু শিখে ফেলছেন। 🤩🤩🤩

এবার আপনার জন্য আরেকটি ইন্টারেষ্টিং উদাহরণ দি-

 def print_square(number):
    for i in range(number):
        for j in range(number):
            print("*")
        print()

এখানে আমরা একটি নেস্টেড ফর লুপ দিয়ে একটি বর্গ আঁকছি। আশা করি আপনারা সবাই জানেন কিভাবে নেস্টেড ফর লুপ কাজ করে। তাহলে এখানে বিগ ও কেমন হবে? প্রথম ফর লুপ টি কতবার চলবে? নম্বর টি যত হবে ততবার নিশ্চয়। সেকেন্ড ফর লুপ টি ফার্স্ট ফর লুপ এর প্রত্যেক টি ইটারেশন এর জন্য নম্বর টি যত ততবার চলবে। তাহলে যদি ফার্স্ট ফর লুপ টি চলে "n" বার এবং সেকেন্ড ফর লুপ টি ফার্স্ট ফর লুপ এর প্রত্যেক টি ইটারেশন এর জন্য চলে “n” বার তারমানে নিশ্চয় গুনফল হবে n * n। দেখুন প্রথম উদাহরণ এ ও আমরা n * 1 করেছিলাম কারণ ওখানে ফর লুপ এর ভিতরে ১ টি স্টেপ ছিল। এখানে যেহেতু ফর লুপ এর ভিতরে "n" টি স্টেপ আছে সেহেতু আমরা n * n = n^2 ধরবো বিগ ও। এরপর আমরা একটি print() লিখেছি এটি যেহেতু প্রথম ফর লুপ এর ভেতর সেহেতু আমরা n * 1 = n যোগ করবো বিগ ও তে। তারমানে ফাইনাল বিগ ও হবে- O(n + n^2)।

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

এখন আপনার জন্য একটি এক্সারসাইজ দিতে চাই। উত্তর ও আমি দিয়ে দিবো কিন্তু উত্তর না দেখে আগে ১০ মিনিট নিজে নিজে বের করার চেষ্টা করুন উত্তর কি হতে পারে-

def sum(arr):
    sum = 0
    for i in range(len(arr)):
        sum += arr[i]

    for j in range(len(arr)):
        sum += arr[j]

এখানে আমরা কোনো একটা বিচিত্র কারণে দুইবার পর পর লুপ করছি (এটি কিন্তু নেস্টেড লুপ না) এবং এরে র প্রত্যেকটি আইটেম কে sum এর সাথে যোগ করছি দুইটি লুপেই।

উপরের প্রব্লেম টি সল্ভ করতে পারলে আপনাকে আরো দুইটি প্রব্লেম সল্ভ করতে দি যেটা আপনার এই পর্বের লার্নিং তাকে একদম পাকা পোক্ত করবে-

def sum_of_two_array(arr1, arr2):
    sum1 = 0
    sum2 = 0
    for i in range(len(arr1)):
        sum1 += arr[i]

    for j in range(len(arr2)):
        sum2 += arr[j]

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

শেষ প্রব্লেম-

def print_hash(arr1, arr2):
    for i in range(len(arr1)):
        for j in range(len(arr2)):
            print("#")

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

আশা করি সবগুলো প্রব্লেম সল্ভ করতে পেরেছেন। আমি এখন উত্তর বলে দিচ্ছি-

১. O(2n)
কেননা এখানে আমরা দুইটা ফর লুপ পর পর করছি। প্রতিটি ফর লুপ এ যদি n স্টেপ নি তাহলে যোগফল O(n + n) = O(2n) হবে।

২. O(n + m)
নোট: এখানে আপনি "m" না ধরে যেকোনো অক্ষর ধরে নিতে পারেন। আপনার টি ও সঠিক হবে।
এখানে O(n + m) কারণ এখানে দুইটি ফর লুপ পর পর করা হচ্ছে কিন্তু এরে দুইটি আলাদা তাই আমরা দুইটি আলাদা অক্ষর নিয়েছি।

৩. O(n * m)
এখানে নেস্টেড ফর লুপ হয়েছে। কিন্তু দুইটি ভিন্ন এরের উপর। তারমানে প্রথম ফর লুপ এর প্রতিটি ইটারেশন এর জন্য দ্বিতীয় ফর লুপ টি “m” বার চলবে। প্রথম ফর লুপ টি যদি “n” বার চলে তাহলে মোট স্টেপ হবে n * m

আপনি এখন বিগ ও র বেসিক টুকু পারেন। এখন আমরা কথা বলবো কিভাবে বিগ ও টি সিম্পলিফায় করবেন। ফার্স্ট এই আমি রুলস গুলো বলি -
১. Worst Case
২. Remove Constants
৩. Different Terms for inputs
৪. Drop non dominants

রুল ১: Worst Case
আপনি যখন একটি এলগোরিদম এর বিগ ও বের করবেন তখন আপনাকে সবসময় সবচেয়ে প্রতিকূল অবস্থায় এলগোরিদম টি কয়টি স্টেপ নিবে সেটি বের করতে হবে। একটা উদাহরণ দি-

def search(numbers, target):
    for i in range(len(numbers)):
        if numbers[i] == target:
            return  i

এই কোড টি তে আমরা একটি নির্দিষ্ট নম্বর খুঁজছি একটি এরের ভিতর। এখন এখানে বিগ ও কেমন হবে? মনে করুন টার্গেট নম্বর টি এরের একদম শুরুতে আছে। তাহলে কিন্তু আমরা একটি স্টেপ নিয়েই নম্বর টি পেয়ে যাবে তারমানে বিগ ও হবে O(1). কিন্তু যদি টার্গেট নম্বর টি এরের একদম শেষে থাকে তাহলে কি হবে? তখন আমাদের পুরো এরেটি লুপ করতে হবে তারমানে এরেটিতে যতগুলো আইটেম আছে ততগুলো স্টেপ অর্থাৎ O(n) এখানে তাহলে আসল বিগ ও টি কেমন হবে? এখানে বিগ ও হবে O(n) কারণ বিগ ও নিয়ে কথা বলার সময় আমরা সবসময় Worst Case টি ভাবি। কারণ আমরা যদি worst case এর জন্য একটি এলগোরিদম ইফিসিয়েন্ট বানাতে পারি তাহলে অন্য case এর জন্য এমনিই ইফিসিয়েন্ট হয়ে যাবে।

রুল ২: Remove Constants
আপনার এলগোরিদম থেকে কোনো কনস্ট্যান্ট থাকলে সেটি রাখার প্রয়োজন নেই। একদম ফার্স্ট প্রব্লেম দিয়ে এটি বুঝিয়ে বলি-

def sum(arr):
    sum = 0
    for i in range(len(arr)):
        sum += arr[i]

    for j in range(len(arr)):
        sum += arr[j]

আমরা দেখেছিলাম এর বিগ ও- O(2n) আমাদের সেকেন্ড রুল অনুযায়ী আমরা এখন থেকে 2 বাদ দিয়ে দিবো তারমানে আমাদের আসল বিগ ও হবে O(n)

রুল ৩: Different Terms for inputs
এই রুল টি আমরা আগেই শিখেছি। প্রব্লেম ২ এবং ৩ এ এই রুল টি ব্যবহার করা হয়েছে। আমি আপনাদের প্রব্লেম ৩ দিয়ে আরেকবার বুঝিয়ে দি-

def print_hash(arr1, arr2):
    for i in range(len(arr1)):
        for j in range(len(arr2)):
            print("#")

এখানে দুইটি ইনপুট এরে দেয়া হয়েছে তারমানে আমাদের দুইটি এরে র জন্য দুইটি আলাদা অক্ষর বা টার্ম ব্যবহার করতে হবে। এখানে বিগ ও হবে O(n * m).

রুল ৪: Drop non dominants
আমরা অনেক আগে একটি উদাহরণ দেখেছিলাম-

 def print_square(number):
    for i in range(number):
        for j in range(number):
            print("*")
        print()

এখানে আমরা বিগ ও বের করেছিলাম- O(n + n^2). এখানে "n" কিন্তু "n^2" এর থেকে ছোট। তারমানে এখানে n^2 সবচেয়ে বেশি প্রভাব ফেলবে তাই আমরা "n" টিকে বাদ দিয়ে দিবো। এখানে আসল বিগ ও হবে- O(n^2)

এই ছিল আমাদের চার টি রুলস। আপনি এখন যেকোনো এলগোরিদম এর বিগ ও বের করতে পারবেন। দ্বিতীয় পর্বে আমরা কিছু বিখ্যাত বিগ ও নিয়ে আলোচনা করবো।

আশা করি আপনাদের বিগ ও সম্পর্কে ভয় টি এখন কেটেছে। দ্বিতীয় পর্বে আবার দেখা হবে। সবার প্রোগ্রামিং যাত্রা সুন্দর হোক 😃😃😃