ফাংশনের গ্রোথ রেট

১ · আটটি প্রমিত গ্রোথ ক্লাস

অ্যালগরিদম অ্যানালাইসিসে ইনপুট সাইজ $n$ বাড়লে রানটাইম কীভাবে বাড়ে তা বর্ণনা করতে কয়েকটি নির্দিষ্ট ফাংশন বারবার দেখা যায়। এদের মধ্যে $n \to \infty$ হলে একটি কঠোর ক্রম প্রতিষ্ঠিত আছে:

$$1 \;\ll\; \log n \;\ll\; n \;\ll\; n\log n \;\ll\; n^2 \;\ll\; n^3 \;\ll\; 2^n \;\ll\; n!$$

এখানে $f(n) \ll g(n)$ মানে "$g(n)$, $f(n)$-এর চেয়ে অসীমগুণ দ্রুত বাড়ে ($n$ যথেষ্ট বড় হলে)" — এটি L07-এ সংজ্ঞায়িত হওয়া little-o নোটেশনেরই একটি প্রাথমিক ইঙ্গিত। আপাতত এটিকে "বাম পাশেরটি ডান পাশেরটির চেয়ে ধীরে বাড়ে" হিসেবে পড়ুন।

২ · কোড সেল — প্রকৃত মান গণনা ও ক্রসওভার পয়েন্ট বের করা

নিচের কোড সেলে প্রতিটি ফাংশনের প্রকৃত মান $n = 1, 2, 4, 8, 16, 32$-এ গণনা করা হয়েছে, এবং তারপর একটি find_permanent_crossover ফাংশন লেখা হয়েছে যা কম্পিউটেশনালি খুঁজে বের করে ঠিক কোন $n$ থেকে একটি ফাংশন আরেকটির চেয়ে চিরতরে বড় থাকে (নির্দিষ্ট একটি পরীক্ষার সীমা পর্যন্ত)।

import math

def const_f(n): return 1
def log_f(n): return math.log2(n) if n >= 1 else 0
def lin_f(n): return n
def linlog_f(n): return n * math.log2(n) if n >= 1 else 0
def quad_f(n): return n ** 2
def cube_f(n): return n ** 3
def exp_f(n): return 2 ** n
def fact_f(n): return math.factorial(n)

sizes = [1, 2, 4, 8, 16, 32]
header = f"{'n':>4} | {'log n':>8} | {'n':>6} | {'n log n':>10} | {'n^2':>8} | {'n^3':>10} | {'2^n':>14} | {'n!':>22}"
print(header)
for n in sizes:
    print(f"{n:>4} | {log_f(n):>8.2f} | {lin_f(n):>6} | {linlog_f(n):>10.2f} | "
          f"{quad_f(n):>8} | {cube_f(n):>10} | {exp_f(n):>14} | {fact_f(n):>22}")

def find_permanent_crossover(f, g, max_n=60):
    # সবচেয়ে ছোট n বের করে যেখান থেকে f(m) > g(m) সবসময় সত্য থাকে (n থেকে max_n পর্যন্ত)
    for n in range(1, max_n + 1):
        if all(f(m) > g(m) for m in range(n, max_n + 1)):
            return n
    return None

pairs = [
    ("log n", log_f, "১ (ধ্রুবক)", const_f),
    ("n log n", linlog_f, "n", lin_f),
    ("2^n", exp_f, "n^3", cube_f),
    ("n!", fact_f, "2^n", exp_f),
]

print("\nক্রসওভার পয়েন্ট (n=60 পর্যন্ত পরীক্ষা করে):")
for name_f, f, name_g, g in pairs:
    n0 = find_permanent_crossover(f, g)
    print(f"{name_f} > {name_g}  চিরতরে সত্য n = {n0} থেকে")

৩ · কেন এটি গুরুত্বপূর্ণ — RAM মডেলের সাথে সংযোগ

L04-এ আমরা দেখেছি RAM মডেলে প্রতিটি মৌলিক অপারেশন $O(1)$ সময় নেয় বলে ধরে নেওয়া হয় — তাই একটি অ্যালগরিদমের "গতি" বোঝাতে আমরা মোট অপারেশন সংখ্যা গণনা করি, এবং সেই গণনাটি সাধারণত এই আটটি ক্লাসের একটির সাথে মিলে যায়। বাস্তব জগতে পার্থক্যটি বিশাল: $n = 1{,}000{,}000$ হলে $\log_2 n \approx 20$, $n\log_2 n \approx 2 \times 10^7$, $n^2 = 10^{12}$ — আধুনিক কম্পিউটারেও এটি সেকেন্ডের বদলে ঘণ্টা লাগাতে পারে। আর $2^n$ বা $n!$-এর মতো ক্লাসে $n=1{,}000{,}000$ ব্যবহারিকভাবে কল্পনাতীত — মহাবিশ্বের বয়সের চেয়েও বেশি সময় লাগবে।