Big-O تصف كيف ينمو وقت تشغيل الخوارزمية أو استهلاك الذاكرة مع نمو حجم الإدخال n. وهي تعكس السلوك التقاربي في الحالة الأسوأ، وتتجاهل الثوابت والحدود الأقل أهمية.
نحن نهتم بمعدل النمو، وليس عدد الخطوات الفعلي. O(2n + 5) ببساطة O(n) لأنه عندما ينمو n بشكل كبير، تتوقف الثوابت والحدود الأصغر عن الأهمية.
| Big-O | الاسم | مثال |
|---|
| O(1) | ثابت | البحث عن عنصر في مصفوفة |
| O(log n) | لوغاريتمي | البحث الثنائي |
| O(n) | خطي | مسح قائمة |
| O(n log n) | خطي لوغاريتمي | ترتيب الدمج |
| O(n²) | تربيعي | حلقات متداخلة |
| O(2ⁿ) | أسي | المجموعات الجزئية الساذجة |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
Big-O تخفي الثوابت: خوارزمية O(n) بثابت كبير جداً قد تخسر مقابل O(n log n) على المدخلات الصغيرة. كما يجب تتبع تعقيد المساحة، وليس الوقت فقط.
Big-O تتيح لك مقارنة الخوارزميات دون تشغيلها أو القلق بشأن الأجهزة.
هي تتنبأ بأي الحلول تبقى عند نمو المدخلات من مئات إلى ملايين — الفرق بين ميزة قابلة للتوسع وأخرى تتجاوز المهلة الزمنية.
هي المفردات التي يستخدمها كل مهندس للتفكير في الأداء.