نماد مرتبه زمانی

Big O Notation روشی برای توصیف کران بالای رشد هزینه یک الگوریتم با افزایش اندازه ورودی است. معمولاً هزینه زمان یا حافظه را نسبت به n بررسی می‌کنیم.

از تعریف تا کاربرد

پیمایش همه عناصر آرایه معمولاً O(n) و دسترسی مستقیم به عنصر آن در بسیاری از پیاده‌سازی‌ها O(1) است. جست‌وجوی دودویی روی داده مرتب O(log n) دارد.

Big O زمان واقعی اجرا را بر حسب ثانیه نمی‌گوید. ضرایب ثابت، حافظه و رفتار سخت‌افزار نیز برای تصمیم مهندسی مهم‌اند.

مقایسه مرتبه زمانی الگوریتم‌ها

# O(n): scan all items
found = any(item.id == target for item in items)

# Average O(1) hash lookup after building index
by_id = {item.id: item for item in items}
found = target in by_id

Big O نرخ رشد هزینه با بزرگ شدن ورودی را توصیف می‌کند و زمان واقعی میلی‌ثانیه نیست. ساخت دیکشنری هم هزینه حافظه و زمان اولیه دارد.