জটিলতা ও বিশ্লেষণ৬ মিনিট পড়া

বিগ-ও, থিটা, ওমেগা (Big-O, Theta, Omega)

অতিথির সংখ্যা বাড়লে আপনার রান্নার রেসিপি কতটা ধীর হয়ে যায়?

O(1) constant:সবসময় একই সময় (Same time, always)O(log n) logarithmic:খুব ধীরগতিতে বাড়ে (Grows very slowly)O(n) linear:ইনপুটের সাথে সমানুপাতিক হারে বাড়ে (Grows with input)O(n²) quadratic:খুব দ্রুত ধীর হয়ে যায় (Slows fast)

ধরুন আপনি একটি ডিনার পার্টির জন্য রান্না করছেন। আপনি ২ জনের খাবার বানান আর ২০০ জনেরই বানান — একটি গ্রিলড চিজ বানাতে আপনার প্রায় একই সময় লাগে — আপনি শুধু আরও বেশি চিজ গ্রিলের ওপর একসাথে বসিয়ে দেন। এটিই হলো \(O(1)\): কনস্ট্যান্ট টাইম বা ধ্রুবক সময়, পরিমাণ বা সাইজ যাই হোক না কেন।

কিন্তু যদি রেসিপিতে বলা থাকে যে, "প্রতিটি ডিশ বা খাবারের স্বাদ নিন এবং অন্য প্রতিটি খাবারের স্বাদের সাথে তার তুলনা করুন", তবে ২০০ জন মানুষের জন্য রান্না করার মানে হলো আপনাকে অসংখ্যবার খাবারের স্বাদ তুলনা করে দেখতে হবে। এটি হলো \(O(n^2)\): অতিথির সংখ্যা বাড়ার সাথে সাথে কাজের পরিমাণ অস্বাভাবিকভাবে অনেকগুণ বেড়ে বা বিস্ফোরিত হয়ে যায়।

বিগ-ও নোটেশন (Big-O notation) হলো মূলত এই বৃদ্ধির হার বা গ্রোথ রেটকে (growth rate) প্রকাশ করার একটি উপায় — অর্থাৎ ইনপুট যত বড় হবে, অ্যালগরিদমে ঠিক ততটাই আনুপাতিকভাবে বাড়তি কতগুলো ধাপ প্রয়োজন হবে? আমরা সঠিক বা একদম নিখুঁত মিলিসেকেন্ড নিয়ে মাথা ঘামাই না (কারণ আপনার মেশিনের প্রসেসরের ওপর তা নির্ভর করে)। আমরা মূলত এই বৃদ্ধির ধরন বা আকার (shape) নিয়ে চিন্তা করি।

মূল ধারণা: ছোটখাটো বিস্তারিত বাদ দিন (Drop the Details)

যদি একটি অ্যালগরিদম 3n² + 100n + 42 টি ধাপ নেয়, তবে বিগ-ও এর ভাষায় তা সহজভাবে \(O(n^2)\) হয়ে যায়। এর কারণ হলো: যখন n এর মান এক মিলিয়ন বা দশ লাখ হয়, তখন ওই \(n^2\) টার্ম বা পদটি অন্য সব কিছুকে ছাড়িয়ে যায় বা তুচ্ছ প্রমাণ করে। তাই আমরা কনস্ট্যান্ট বা ধ্রুবকগুলোকে এবং ছোট টার্ম বা পদগুলোকে বাদ দিই, এবং শুধুমাত্র সবচেয়ে প্রভাবশালী অংশটিই হিসেবের জন্য রেখে দিই।

দুটি নিয়ম মনে রাখা প্রয়োজন: (১) কনস্ট্যান্ট বা ধ্রুবক বাদ দিন — 5n মানে হলো \(O(n)\)। (২) ছোট টার্ম বা পদ বাদ দিন — \(n^2\) + n মানে হলো \(O(n^2)\)। ধাপে ধাপে বলা কাজগুলো (Sequential steps) আনুপাতিকভাবে যোগ হয়, যেখানে নেস্টেড লুপগুলো (nested loops) গুণ হয়।

সবচেয়ে সাধারণ কমপ্লেক্সিটি বা জটিলতাগুলো

\(O(1)\) — কনস্ট্যান্ট (Constant)। ইনডেক্স ধরে অ্যারের কোনো এলিমেন্টকে বের করা। ইনপুট যাই হোক না কেন এর স্পিড সবসময় একই থাকে।

\(O(\log n)\) — লগারিদমিক (Logarithmic)। সাজানো বা সর্টেড লিস্টের ওপর বাইনারি সার্চ (Binary search) চালানো। প্রতিটি ধাপে মূল সমস্যাটি দুই ভাগে বা অর্ধেক ভাগ হয়ে যায়, তাই ইনপুট বিলিয়ন সংখ্যক হলেও এটি সমাধান করতে সময় লাগবে মাত্র ~৩০টি ধাপ।

\(O(n)\) — লিনিয়ার (Linear)। প্রতিটি আইটেমকে একবার করে স্ক্যান বা চেক করা। ইনপুট দ্বিগুণ করুন, তাহলে সময়ও দ্বিগুণ হবে।

\(O(n \log n)\) — লিনিয়ারিদমিক (Linearithmic)। মার্জ সোর্ট (Merge sort), হিপ সোর্ট (heap sort)। তুলনাভিত্তিক বা কম্পারিজন-বেজড (comparison-based) সর্টিংয়ের জন্য এটি অত্যন্ত চমৎকার জায়গা বা সুইট স্পট (sweet spot)।

\(O(n^2)\) — কোয়াড্রেটিক (Quadratic)। লুপের ভেতরে লুপ (A loop inside a loop)। ইনপুট ১০ গুণ (10x) বাড়ার অর্থ সময় ১০০ গুণ (100x) বেড়ে যাওয়া।

\(O(2^n)\) — এক্সপোনেনশিয়াল (Exponential)। ব্রুট-ফোর্স পদ্ধতিতে সব সাবসেট স্ক্যান বা চেক করা। ইনপুটের মান ~৩০ এর বেশি হলে এটি একেবারেই অকার্যকর বা অসম্ভব হয়ে পড়ে।

বিগ-ও (Big-O), বিগ-ওমেগা (Big-Omega), বিগ-থিটা (Big-Theta)

বিগ-ও হলো আপার বাউন্ড (upper bound) — অর্থাৎ এটি সবচেয়ে খারাপ পরিস্থিতিতে কতটা সময় নিতে পারে তা বোঝায়। বিগ-ওমেগা (Ω) হলো লোয়ার বাউন্ড (lower bound) — অর্থাৎ এটি সবচেয়ে সেরা পরিস্থিতিতে কতটা দ্রুত কাজ করতে পারে। বিগ-থিটা (Θ) হলো এই দুইটির মাঝখানে থাকা অবস্থা: এটি বোঝায় যে অ্যালগরিদমের বৃদ্ধির হার ঠিক ওই ফাংশনটির মতোই হবে। মার্জ সোর্টের কমপ্লেক্সিটি হলো সব ক্ষেত্রেই \(\Theta(n \log n)\) — তা সেরা, সবচেয়ে খারাপ, বা গড় ক্ষেত্র (average) যাই হোক না কেন।

দ্রষ্টব্য: বিগ-ও মূলত একটি স্পিড লিমিট সাইনের মতো কাজ করে — এটি আপনাকে সবচেয়ে খারাপ পরিস্থিতি বা ওয়ার্স্ট কেসের (worst case) কথা বলে, বরং এর সাধারণ কোনো গতির কথা বলে না। কোনো অ্যালগরিদম যা \(O(n)\) হয়, সেটি সাধারণত অনেক বেশি দ্রুতগতিতে চলতে পারে, তবে এটি কখনোই লিনিয়ার গ্রোথের চেয়ে (linear growth) বেশি ধীরগতির হবে না।

কোডে বিগ-ও দেখা (Seeing Big-O in Code)

import time, math

def o_1(arr):        # O(1)
    return arr[0]

def o_n(arr):        # O(n)
    total = 0
    for x in arr:
        total += x
    return total

def o_n2(arr):       # O(n²)
    count = 0
    for i in arr:
        for j in arr:
            count += 1
    return count

arr = list(range(1000))
print(o_1(arr))          # 0  — always 1 step
print(o_n(arr))          # 499500  — 1000 steps
print(o_n2(arr))         # 1000000  — 1,000,000 steps