رده‌های رایج پیچیدگی

فرمول

O (1) < O (lo g n) < O (n) < O (n lo g n) < O (n^{2}) < O (2^{n})

زنجیرهٔ رشد: هر رده برای ورودی بزرگ، دنیایی با ردهٔ بعد فرق دارد

هر رده یعنی چه؟

$O (1)$: ثابت — دسترسی ایندکسی لیست، عضویت set (میانگین)
$O (lo g n)$: لگاریتمی — جست‌وجوی دودویی روی دادهٔ مرتب
$O (n)$: خطی — یک پیمایش کامل: جست‌وجوی خطی، map ساده
$O (n lo g n)$: خطی-لگاریتمی — مرتب‌سازی‌های خوب مثل sorted
$O (n^{2})$: درجه‌دوم — حلقهٔ تودرتو روی همان داده
$O (2^{n})$: نمایی — جست‌وجوی فراگیرِ همهٔ زیرمجموعه‌ها — برای n بزرگ ناممکن

شهودِ مقیاس: اگر n ده برابر شود، هزینهٔ $O (n)$ ده برابر و هزینهٔ $O (n^{2})$ صد برابر می‌شود. برای n=۱۰۰۰۰۰ تفاوتِ «یک ثانیه» و «سه ساعت» همین‌جاست.

پیش‌نیازها