اعمال مفهوم پیچیدگی روی مثال‌های واقعی
حالا که با نماد O بزرگ آشنا شدیم، بیایید الگوریتم‌هایی که در این دوره دیدیم را از نظر پیچیدگی زمانی مرور کنیم. الگوریتم پیدا کردن بزرگ‌ترین عدد، فقط یک حلقه‌ی ساده روی n عنصر دارد، پس پیچیدگی آن O(n) است. الگوریتم جستجوی خطی نیز دقیقاً همین ساختار را دارد و O(n) است.
الگوریتم مرتب‌سازی حبابی اما یک حلقه‌ی تودرتو دارد: برای هر عنصر بیرونی، یک حلقه‌ی داخلی کامل اجرا می‌شود. به همین دلیل پیچیدگی آن O(n²) است، که به‌مراتب کندتر از الگوریتم‌های خطی است، به‌خصوص وقتی حجم داده زیاد شود.
برای درک بهتر، جدول زیر تعداد تقریبی عملیات را برای اندازه‌های مختلف ورودی نشان می‌دهد:
| n | O(n) | O(n²) |
|---|---|---|
| 10 | 10 | 100 |
| 100 | 100 | 10,000 |
| 1,000 | 1,000 | 1,000,000 |
همان‌طور که در جدول می‌بینید، با افزایش n از ۱۰ به ۱۰۰۰، الگوریتم خطی فقط ۱۰۰ برابر کندتر می‌شود، در حالی که الگوریتم درجه‌دوم ۱۰۰۰۰ برابر کندتر می‌شود. همین تفاوت است که در نرم‌افزارهای واقعی با حجم داده‌ی زیاد، انتخاب الگوریتم مناسب را به یک تصمیم بسیار مهم تبدیل می‌کند.