هذا المقال لمستوى: مبتدئ
لو كودك بيلاقي النتيجة في جزء من الثانية على 100 عنصر، وبيتجمّد لما البيانات توصل مليون، المشكلة مش في السيرفر ولا في لغة البرمجة. المشكلة في كيفية نمو عدد العمليات مع حجم البيانات. الأداة اللي بتقيس ده اسمها Big O، وبعد المقال ده هتبقى قادر تبص على أي حلقة وتحكم عليها قبل ما تكسّر عندك الإنتاج.
الـ Big O: مقياس نمو الكود مش سرعته
المشكلة باختصار
معظم المبتدئين بيقيسوا الكود بالثواني على جهازهم. ده مقياس خدّاع. الكود اللي بياخد 10 مللي ثانية على 1000 صف ممكن ياخد 3 دقايق على مليون صف، والكود التاني ياخد نفس الـ 10 مللي ثانية على المليون. الفرق بينهم مش في السرعة اللحظية، ده في معدّل النمو. Big O بيوصف المعدّل ده، فبيقولك مقدمًا مين اللي هيقف قدامك في الإنتاج.
مثال قبل ما نعقّدها: دفتر التليفونات
تخيّل معاك دفتر تليفونات فيه مليون اسم مرتّبين أبجديًا، وعايز تلاقي رقم "محمود".
الطريقة الأولى: تبدأ من أول صفحة وتقلّب واحدة واحدة لحد ما توصل. لو "محمود" في الآخر، انت قلّبت مليون صفحة. لو الأسماء بقت 2 مليون، هتقلّب ضعف. عدد الخطوات بيزيد بنفس نسبة زيادة البيانات. ده اللي بنسمّيه O(n).
الطريقة التانية: تفتح الدفتر من النص. لو "محمود" بعد الصفحة دي، تتجاهل النص الأول كله وتفتح نص النص التاني، وهكذا. كل خطوة بتقسّم المتبقّي على 2. مليون اسم بتوصله في حوالي 20 خطوة بس. لو بقوا 2 مليون، بتحتاج 21 خطوة، مش 40 مليون. ده O(log n)، وده سر الـ binary search والـ database index.
خلّي الصورة دي في دماغك: O(n) بيمشي مع البيانات خطوة بخطوة، وO(log n) بيقسّمها على 2 كل مرة. الأول بيتعب بسرعة، والتاني بالكاد بيحس بالزيادة.
يعني إيه Big O بالظبط (التعريف العلمي)
Big O بيصف الحد الأعلى لمعدّل نمو عدد العمليات بالنسبة لحجم المدخلات n، لما n بيكبر. بنتجاهل الثوابت والتفاصيل الصغيرة، لأنها بتختفي قدام النمو نفسه. يعني حلقة بتعمل 3n + 50 عملية بنكتبها O(n)، لأن الـ 3 والـ 50 مبيغيّروش شكل النمو.
الترتيب من الأحسن للأسوأ اللي هتقابله كتير: O(1) ثابت لا يتأثر بالحجم، بعده O(log n)، بعده O(n)، بعده O(n log n) بتاع الفرز الجيد، وأخيرًا O(n²) اللي بيطلع من حلقة جوّه حلقة. بص على الرسم فوق: عند n = مليون، O(n) بيعمل مليون عملية، لكن O(n²) بيعمل تريليون. ده الفرق بين استعلام بيرجع في لحظة واستعلام بيوقّع السيرفر.
مثال تشغّله بنفسك: list في مقابل set
الكلام النظري مايكفيش. جرّب الكود ده في بايثون. بيدوّر على عنصر مرة في list ومرة في set:
import time
N = 1_000_000
data_list = list(range(N))
data_set = set(data_list)
target = N - 1
t = time.perf_counter()
_ = target in data_list
print("list:", (time.perf_counter() - t) * 1000, "ms")
t = time.perf_counter()
_ = target in data_set
print("set :", (time.perf_counter() - t) * 1000, "ms")
على جهاز عادي هيطلعلك رقم قريب من ده:
list: 9.8 ms
set : 0.001 ms
نفس السؤال، ونفس البيانات، بس set أسرع حوالي 9000 مرة. السبب إن x in list تعقيده O(n) لأنه بيمشي على العناصر، بينما x in set تعقيده O(1) في المتوسط لأنه بيحسب هاش المفتاح ويروح لمكانه على طول. دلوقتي تخيّل إن الفحص ده جوّه حلقة على مليون عنصر: list بيخلّيها O(n²) والبرنامج بيتجمّد، وset بيخلّيها O(n) وبتخلص في ثانية.
الـ trade-off: مفيش حاجة ببلاش
الـ set أسرع في البحث، بس بتدفع تمن. بتكسب بحث O(1)، وبتخسر: ذاكرة أكتر (بيخزّن جدول هاش مش مجرد عناصر متتابعة)، وبتفقد الترتيب، والعناصر لازم تكون hashable. كمان بناء الـ set نفسه تكلفته O(n) مرة واحدة. الافتراض إنك هتبحث كتير في نفس البيانات، فالتكلفة دي بتترد أضعاف. لو هتبحث مرة واحدة بس، بناء الـ set غالبًا مش مستاهل.
متى متشغلش بالك بالـ Big O
Big O بيتكلم عن السلوك لما n بيكبر. لو الـ n بتاعتك صغيرة وثابتة — قايمة فيها 20 عنصر مثلًا — الفرق بين O(n) وO(1) مش هيتحس، وأحيانًا الـ list الأبسط بتكون أسرع فعليًا لأن الثوابت المخفية أقل. متحوّلش كودك لأصعب في القراءة عشان تكسب ميكروثانية على بيانات مش هتكبر. الـ Big O أداة قرار للأجزاء اللي بتكبر وبتتكرر، مش لكل سطر.
المصادر
- توثيق بايثون الرسمي لتعقيد العمليات على list وset وdict: wiki.python.org/moin/TimeComplexity
- Big-O Cheat Sheet لتعقيدات الخوارزميات وهياكل البيانات الشائعة: bigocheatsheet.com
- التعريف الرسمي لترميز Big O: en.wikipedia.org/wiki/Big_O_notation
- شرح جداول الهاش وليه البحث فيها O(1) في المتوسط: en.wikipedia.org/wiki/Hash_table
الخطوة التالية
افتح أبطأ جزء في كودك ودوّر على أي in بيتنفّذ جوّه حلقة على list كبيرة. حوّل الـ list دي لـ set قبل الحلقة، وقيس الزمن قبل وبعد بنفس السكربت اللي فوق. لو الفرق كان كبير زي المثال، انت لسه لقيت O(n²) مخبّي كان بيستنّى يكسّر عندك الإنتاج.