مستوى المقال: مبتدئ. لو انت لسه بادئ في البرمجة وسمعت كلمة "Big-O" وحسيت إنها طلاسم، المقال ده ليك. هنشرحها بمثال بسيط الأول، وبعدين نرجع للتعريف العلمي الدقيق.
تعقيد الوقت Big-O: إزاي تعرف إن كودك هيبطأ قبل ما المشروع يكبر
هتكسب حاجة واحدة من المقال ده: هتبص على أي دالة وتعرف هتفضل سريعة ولا هتخنق لما البيانات تكبر، من غير ما تشغّلها أصلًا. دي أهم مهارة بتفرّق بين مبتدئ وبين حد بيكتب كود بيكبر.
المشكلة باختصار
الكود بتاعك بيشتغل تمام دلوقتي. عندك 100 مستخدم في قاعدة البيانات، والصفحة بتفتح في جزء من الثانية. بعد سنة بقى عندك مليون مستخدم، ونفس الصفحة بقت تاخد 30 ثانية. مفيش حاجة اتغيّرت في الكود، السيرفر نفسه، بس البيانات كبرت. المشكلة مش في السيرفر، المشكلة في إن الخوارزمية بتاعتك بتكبّر شغلها بسرعة أكبر من البيانات نفسها. Big-O هي اللغة اللي بتوصف ده بالظبط.
الأول بمثال: دليل التليفون
تخيّل معاك دليل تليفون ورقي فيه مليون اسم، مرتّبين أبجديًا. عايز تلاقي رقم "محمود".
- الطريقة الأولى: تفتح من أول صفحة وتقرأ اسم اسم لحد ما توصل. لو الاسم في الآخر، ممكن تقلّب مليون صفحة. ده اسمه O(n): الشغل بيزيد بنفس معدل زيادة البيانات. ضِعف الأسماء يعني ضِعف الوقت.
- الطريقة التانية: تفتح في النص، تبص الاسم اللي قدامك قبل ولا بعد "محمود"، وترمي نص الدليل اللي مالكش فيه، وتكرّر. مليون اسم بتخلص في حوالي 20 خطوة بس. ده اسمه O(log n): كل خطوة بتقسم المشكلة على 2.
الفرق؟ في المليون، الأولى 1,000,000 خطوة، والتانية 20 خطوة. نفس المشكلة، فرق 50 ألف ضعف. دي فكرة Big-O كلها في جملة: مش بتقيس الوقت بالثواني، بتقيس إزاي الوقت بيكبر مع البيانات.
دلوقتي التعريف العلمي
Big-O هي طريقة لوصف أسوأ حالة لنمو عدد العمليات في خوارزمية بالنسبة لحجم المدخل، اللي بنسمّيه n. إحنا بنتجاهل الثوابت والتفاصيل الصغيرة، وبنركّز على الشكل العام للنمو لما n تكبر جدًا. يعني O(2n) وO(n) بنعتبرهم واحد، لأن المهم إنهم بيكبروا خطيًا. الافتراض هنا إن n كبيرة كفاية عشان الفرق في شكل النمو يبقى هو اللي بيحكم، مش الأرقام الصغيرة.
أشهر 5 فئات لازم تحفظها
- O(1) ثابت: نفس عدد الخطوات مهما كبرت البيانات. مثال: الوصول لعنصر في قائمة برقمه
arr[5]. - O(log n) لوغاريتمي: بيكبر ببطء شديد. مثال: البحث الثنائي.
- O(n) خطي: بيكبر بنفس معدل البيانات. مثال: المرور على كل عنصر مرة.
- O(n log n): أفضل ما يمكن لخوارزميات الترتيب العامة زي
sort(). - O(n²) تربيعي: حلقة جوّه حلقة. مثال: مقارنة كل عنصر بكل عنصر. ده بيقتل الأداء بسرعة.
جرّبها بنفسك بالأرقام
الكلام النظري مش كفاية. الكود ده بيقيس الفرق فعليًا بين O(n) وO(n²) وO(1) على نفس البيانات:
import time
def build(n):
return list(range(n))
def linear_search(data, target): # O(n)
for x in data:
if x == target:
return True
return False
def has_duplicate_slow(data): # O(n^2) — حلقة جوه حلقة
for i in range(len(data)):
for j in range(i + 1, len(data)):
if data[i] == data[j]:
return True
return False
n = 20000
data = build(n)
lookup = set(data) # O(1) للبحث بعد البناء
t = time.perf_counter()
linear_search(data, -1) # أسوأ حالة: مش موجود
print("O(n) :", round(time.perf_counter() - t, 4), "ثانية")
t = time.perf_counter()
has_duplicate_slow(data)
print("O(n^2) :", round(time.perf_counter() - t, 4), "ثانية")
t = time.perf_counter()
(-1) in lookup # بحث في set
print("O(1) :", round(time.perf_counter() - t, 6), "ثانية")
على جهاز عادي بتطلع النتيجة قريبة من كده: O(n) حوالي 0.001 ثانية، O(n²) حوالي 12 ثانية، وO(1) حوالي 0.000002 ثانية. لاحظ: لو زوّدت n من 20 ألف لـ 40 ألف، الـ O(n²) مش هتبقى 24 ثانية، هتبقى حوالي 48 ثانية، لأنها بتتربّع. ده اللي بيحصل فعلاً لما مشروع صغير يكبر ويبدأ يخنق فجأة.
سيناريو واقعي
لو عندك صفحة بتعرض قايمة منتجات، وبتشيك على كل منتج لو مكرّر بمقارنته بكل المنتجات التانية، ده O(n²). على 500 منتج، ده ربع مليون مقارنة، بيعدّي بسرعة. على 50 ألف منتج، بقى 2.5 مليار مقارنة، والصفحة هتقف. الحل: حوّل القايمة لـ set واستخدم البحث بـ O(1). نفس النتيجة، بس من ساعة لجزء من الثانية.
الـ trade-off هنا
تحسين الـ Big-O مش ببلاش دايمًا. لما تستخدم set أو dict عشان تنزّل البحث لـ O(1)، بتكسب سرعة، بس بتخسر ذاكرة زيادة لتخزين الهيكل، وبتخسر الترتيب في الحالات القديمة. القاعدة: لو n صغيرة (عشرات أو مئات)، متتعبش نفسك، الفرق مش محسوس والكود الأبسط أحسن. الافتراض إن التحسين يستاهل بيبدأ لما n توصل لعشرات الآلاف وفوق.
متى متشغلش بالك
لو البيانات بتاعتك صغيرة وثابتة، أو الكود بيشتغل مرة واحدة في اليوم في مهمة خلفية، Big-O مش أولوية. O(n²) على 100 عنصر بيخلص في لمح البصر. متعقّدش الكود عشان تحسين مش هتحس بيه. الأولوية للوضوح، والتحسين يجي لما تقيس مشكلة حقيقية، مش قبلها.
الخطوة التالية
افتح أبطأ دالة عندك النهاردة ودوّر على حلقة جوّه حلقة (loop داخل loop) بتلفّ على نفس البيانات. دي غالبًا O(n²). جرّب تحوّلها لبحث بـ set أو dict، وقِس الوقت قبل وبعد بـ time.perf_counter(). لو الفرق كبير، انت لقيت أهم اختناق في كودك.
المصادر
- Cormen, Leiserson, Rivest, Stein — "Introduction to Algorithms" (CLRS), الفصل 3: Growth of Functions، MIT Press.
- Python Software Foundation — TimeComplexity Wiki (تعقيد عمليات list وset وdict): wiki.python.org/moin/TimeComplexity
- Big-O Cheat Sheet — مرجع سريع لتعقيد الخوارزميات وهياكل البيانات: bigocheatsheet.com
- Khan Academy — Asymptotic notation (شرح تمهيدي للـ Big-O، Big-Θ، Big-Ω).