پیچیدگی زمانی و Big O
تحلیل پیچیدگی زمانی با نماد Big O: O(1)، O(log n)، O(n)، O(n log n)، O(n²) و O(2ⁿ) با مثال و جدول مقایسه
چرا تحلیل پیچیدگی؟
چطور بفهمیم الگوریتمی «بهتر» است؟ زمان‌سنجی با ثانیه قابل اعتماد نیست (به سخت‌افزار بستگی دارد). راه‌حل: شمارش تعداد عملیات پایه نسبت به اندازه ورودی n — این همان نماد Big O است.
Big O چیست؟
O(f(n)) نرخ رشد زمان اجرا با بزرگ‌شدن ورودی را نشان می‌دهد. مهم‌ترین قاعده: ثابت‌ها و جمله‌های کوچک‌تر را نادیده بگیریم:
- 3n + 5 ← O(n)
- n² + 10n + 100 ← O(n²)
چون با n بزرگ، جمله غالب بقیه را بی‌اثر می‌کند.
پیچیدگی‌های مهم (از بهترین به بدترین)
O(1) — ثابت
مستقل از اندازه داده؛ همیشه یک عملیات. مثل دسترسی به آرایه با اندیس یا dict پایتون.
O(log n) — لگاریتمی
با هر مرحله، فضای جستجو نصف می‌شود! مثل جستجوی دودویی. برای ۱ میلیون داده فقط ~۲۰ مرحله. فوق‌العاده!
O(n) — خطی
هر عنصر را یک‌بار می‌بینیم. مثل پیمایش لیست یا جستجوی خطی.
O(n log n) — خطی‌لگاریتمی
بهترین ممکن برای مرتب‌سازی مقایسه‌ای. مثل Merge Sort و Quick Sort.
O(n²) — درجه دو
حلقه داخل حلقه روی همه داده‌ها. مثل Bubble Sort. با n=۱۰۰۰۰ یعنی ۱۰۰ میلیون عملیات!
O(2ⁿ) — نمایی
کابوس! مثل حل naive مسئله Fibonacci یا هانوی. فقط برای n کوچک قابل استفاده.
جدول مقایسه رشد
| n | O(1) | O(log n) | O(n) | O(n log n) | O(n²) |
|---|---|---|---|---|---|
| ۱۰ | ۱ | ۳ | ۱۰ | ۳۳ | ۱۰۰ |
| ۱۰۰ | ۱ | ۷ | ۱۰۰ | ۶۶۴ | ۱۰٬۰۰۰ |
| ۱٬۰۰۰ | ۱ | ۱۰ | ۱٬۰۰۰ | ۹٬۹۶۶ | ۱ میلیون |
| ۱ میلیون | ۱ | ۲۰ | ۱M | ۲۰M | ۱ تریلیون! |
به ستون O(n²) در n=۱ میلیون نگاه کنید — یک تریلیون عملیات یعنی ساعت‌ها انتظار!
قواعد محاسبه Big O
- ترتیبی: مجموع مراحل = بزرگ‌ترین جمله: O(n) + O(n²) = O(n²)
- تودرتو: حلقه در حلقه = ضرب: حلقه n تایی در حلقه n تایی = O(n²)
- ثابت‌ها حذف: O(2n) = O(n)
- ورودی‌های مستقل: دو حلقه جدا روی n و m ← O(n + m)
پیچیدگی مکانی
علاوه بر زمان، حافظه هم مهم است: آیا الگوریتم آرایه کمکی می‌سازد؟ Merge Sort حافظه اضافی O(n) می‌خواهد اما Quick Sort معمولاً O(log n).
بهترین، بدترین و میانگین
معمولاً بدترین حالت (Worst Case) گزارش می‌شود چون تضمین می‌دهد. مثلاً جستجوی خطی: بهترین ۱ مقایسه، بدترین n مقایسه ← می‌گوییم O(n).
جمع‌بندی
- Big O نرخ رشد زمان اجرا نسبت به اندازه ورودی است
- ترتیب کیفیت: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
- حلقه تودرتو = ضرب؛ مراحل پشت‌سرهم = بزرگ‌ترین
- بدترین حالت معیار استاندارد تحلیل است
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.