نمادهای مجانبی (Asymptotic Notations): زبان تحلیل الگوریتم‌ها ⏱️📈

نمادهای مجانبی ابزارهای ریاضی هستند که کارایی الگوریتم‌ها را از نظر زمان اجرا و مصرف حافظه توصیف می‌کنند. این نمادها به ما کمک می‌کنند تا رفتار الگوریتم‌ها را وقتی ورودی‌ها بسیار بزرگ می‌شوند (به سمت بی‌نهایت میل می‌کنند) تحلیل کنیم.

1. نمادهای اصلی مجانبی 📌

الف) نماد O بزرگ (Big-O) - حد بالایی سست

• تعریف ریاضی:

  
  f(n) = O(g(n)) اگر ∃ c>0, n₀>0 به طوری که ∀n≥n₀ : 0 ≤ f(n) ≤ c·g(n)
  
  

• تفسیر: "f(n) رشد سریع‌تر از g(n) ندارد"

• مثال:

  • 5n² + 3n + 2 = O(n²)

  • 2n + log n = O(n)

ب) نماد Ω بزرگ (Big-Omega) - حد پایینی سست

• تعریف ریاضی:

  
  f(n) = Ω(g(n)) اگر ∃ c>0, n₀>0 به طوری که ∀n≥n₀ : 0 ≤ c·g(n) ≤ f(n)
  
  

• تفسیر: "f(n) رشد کندتر از g(n) ندارد"

• مثال:

  • n³ - 4n² = Ω(n³)

  • 7n log n = Ω(n log n)

ج) نماد Θ (Big-Theta) - حد دقیق

• تعریف ریاضی:

  
  f(n) = Θ(g(n)) اگر f(n) = O(g(n)) و f(n) = Ω(g(n))
  
  

• تفسیر: "f(n) و g(n) هم‌تراز رشد می‌کنند"

• مثال:

  • ½n² + 5n = Θ(n²)

  • 3n log n + n = Θ(n log n)

2. نمادهای فرعی: small-o و small-omega 🔎

الف) نماد o کوچک (small-o) - حد بالایی شدید

• تعریف ریاضی:

  
  f(n) = o(g(n)) اگر ∀c>0, ∃n₀>0 به طوری که ∀n≥n₀ : 0 ≤ f(n) < c·g(n)
  
  

• تفسیر: "f(n) رشد به مراتب کندتر از g(n) دارد"

• تفاوت با Big-O: در small-o، نرخ رشد به شدت کمتر است (نه برابر)

• مثال:

  • n = o(n²)

  • log n = o(n)

ب) نماد ω کوچک (small-omega) - حد پایینی شدید

• تعریف ریاضی:

  
  f(n) = ω(g(n)) اگر ∀c>0, ∃n₀>0 به طوری که ∀n≥n₀ : 0 ≤ c·g(n) < f(n)
  
  

• تفسیر: "f(n) رشد به مراتب سریع‌تر از g(n) دارد"

• تفاوت با Big-Omega: در small-omega، نرخ رشد به شدت بیشتر است (نه برابر)

• مثال:

  • n² = ω(n)

  • 2ⁿ = ω(n³)

3. مقایسه جامع نمادها ⚖️

4. مثال‌های کاربردی 💻

مثال ۱: تحلیل الگوریتم جستجوی دودویی

def binary_search(arr, target):
    low, high = 0, len(arr)-1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

• تحلیل:

  • بدترین حالت: O(log n)

  • بهترین حالت: Ω(1)

  • نسبت به n²: o(n²) و ω(1)

مثال ۲: تحلیل الگوریتم مرتب‌سازی سریع (QuickSort)

• میانگین حالت: Θ(n log n)

• نسبت به n²: o(n²) (زیرا n log n به مراتب کندتر از n² رشد می‌کند)

• نسبت به n: ω(n) (زیرا n log n به مراتب سریع‌تر از n رشد می‌کند)

5. پیاده‌سازی تحلیلی در پایتون 🐍

بررسی رابطه small-o بین دو تابع

def is_small_o(f, g, n_values):
    for n in n_values:
        if f(n) >= 0.01 * g(n):  # انتخاب c=0.01
            return False
    return True

# بررسی آیا n = o(n²)؟
f = lambda n: n
g = lambda n: n**2
n_values = range(1000, 10000)
print(is_small_o(f, g, n_values))  # True

نمودار مقایسه نمادها

import matplotlib.pyplot as plt
import numpy as np

n = np.linspace(1, 10, 100)
plt.plot(n, n**2, label='g(n) = n²')
plt.plot(n, 3*n**1.5, label='f(n) = 3n^1.5')
plt.xlabel('n')
plt.ylabel('Value')
plt.legend()
plt.show()

📌 تحلیل: 3n^1.5 = o(n²) زیرا منحنی آن به مراتب پایین‌تر از n² باقی می‌ماند.

6. کاربردها و خطاهای رایج ⚠️

کاربردهای کلیدی

• طراحی الگوریتم: انتخاب بین الگوریتم‌های O(n log n) و O(n²)

• تحلیل سیستم‌های بلادرنگ: تضمین O(n) برای پاسخ‌های سریع

• یادگیری ماشین: تحلیل پیچیدگی مدل‌ها

خطاهای متداول

1. اشتباه گرفتن o با O:

   • ❌ گفتن n = O(n²) و n = o(n²) یکسان است (درست: اولی صحیح، دومی هم صحیح اما قوی‌تر)

2. استفاده نادرست از ω:

   • ❌ گفتن n² = ω(n³) (درست: n² = ω(n))

🎯 نتیجه‌گیری

• Big-O/small-o: برای تحلیل حد بالا (سست/شدید)

• Big-Omega/small-omega: برای تحلیل حد پایین (سست/شدید)

• Θ: وقتی حد بالا و پایین برابر باشند

• small-o/ω: روابط سخت‌گیرانه‌تر از O/Ω هستند

پرسش فکری: آیا رابطه 2^n = ω(n^100) برقرار است؟ (پاسخ: ✅ بله، چون توابع نمایی به مراتب سریع‌تر از چندجمله‌ای رشد می‌کنند)