معرفی مقدماتی Big O
نماد O بزرگ (Big O) روشی استاندارد برای توصیف رشد تعداد عملیات یک الگوریتم نسبت به اندازه‌ی ورودی n است، در بدترین حالت ممکن. در این دوره فقط با چند حالت پرکاربرد و ساده آشنا می‌شویم، بدون ورود به اثبات ریاضی دقیق.
| نماد | نام | مثال |
|---|---|---|
| O(1) | ثابت | خواندن اولین عضو یک لیست |
| O(n) | خطی | جستجوی خطی در یک لیست |
| O(n²) | درجه دوم | مرتب‌سازی حبابی |
| O(log n) | لگاریتمی | جستجوی دودویی |
در الگوریتم O(1)، تعداد عملیات مستقل از اندازه‌ی ورودی و همیشه ثابت است. در O(n)، تعداد عملیات با افزایش اندازه‌ی ورودی به همان نسبت افزایش می‌یابد. در O(n²)، مانند مرتب‌سازی حبابی که یک حلقه‌ی تودرتوی دیگر دارد، با دو برابر شدن اندازه‌ی ورودی، تعداد عملیات تقریباً چهار برابر می‌شود.
یک قاعده‌ی ساده برای تخمین پیچیدگی یک قطعه کد این است: هر حلقه‌ی ساده که یک‌بار روی n عنصر اجرا می‌شود، معمولاً O(n) است؛ و هر حلقه‌ی تودرتو که هرکدام تا n تکرار می‌کنند، معمولاً O(n²) است. با این قاعده‌ی ساده، می‌توانید سریعاً پیچیدگی تقریبی بسیاری از الگوریتم‌های ساده را تشخیص دهید.