هذا المقال لمستوى: مبتدئ
لو كودك بيلاقي النتيجة في جزء من الثانية على 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")