الفرز وتحليل التعقيد
درس 8 من 8
8الفرز وتحليل التعقيد (Big O)
أول أداة رسمية لمقارنة الحلول رياضيًا بدل "أشعر أن هذا أسرع"، وأول عائلة خوارزميات فرز حقيقية.
ماذا تشاهد في الرسم: كل خطوة تقارن عمودين متجاورين وتبدّلهما إن كان الأكبر قبل الأصغر، حتى يصير الصف مرتّبًا.
خارطة هذا الجزء
المفاهيم بالترتيب، اضغط أيًّا منها للقفز إليه:
طريقان إلى نفس الفكرة
ترتيب كومة أوراق امتحانات بالأسماء له طرق كثيرة: تقارن كل ورقتين متجاورتين، أو تقسم الكومة نصفين وترتب كل نصف ثم تدمجهما. كلها تصل للنتيجة نفسها، لكن بعضها يأخذ دقيقة وبعضها ساعة حين تكبر الكومة. تحليل التعقيد يقيس هذا الفرق قبل أن تجرّب.
تدوين Big-O يصف نمو الزمن مع حجم المدخل n: الفقاعات bubble والإدراج insertion في O(n^2)، والدمج merge وquick في O(n log n) بالمتوسط. تحسب العمليات في الحالة الأسوأ والمتوسطة، وتنتبه للثبات stable والذاكرة الإضافية.
قبل أن تبدأ
🔁الحلقات المتداخلة
معظم خوارزميات الفرز البسيطة مبنية على حلقة داخل حلقة، تمامًا كما في الجزء الرابع.
الفكرة الجوهرية: ماذا تقيس Big O فعليًا؟
Big O لا تقيس الزمن بالثواني (ذلك يعتمد على سرعة الجهاز)، بل تقيس كيف ينمو وقت التنفيذ (أو استهلاك الذاكرة) مع نمو حجم المُدخل n، في أسوأ الحالات عادة.
شكل 1، كل خطوة يمينًا تعني نموًا أسرع بكثير في الوقت كلما كبر n؛ خوارزمية O(n²) على مليون عنصر أبطأ بمقدار مليون مرة تقريبًا من خوارزمية O(n) على نفس العدد.
11️⃣ O(1): ثابت
نفس الزمن بغض النظر عن حجم المُدخل، مثل الوصول لعنصر مصفوفة بفهرسه المباشر. السبب الميكانيكي: عنوان أي عنصر arr[i] يُحسَب مباشرة بمعادلة واحدة (عنوان البداية + i × حجم العنصر) بلا أي حاجة للمرور على العناصر السابقة، سواء كانت المصفوفة من 10 عناصر أو 10 ملايين، عملية حساب هذا العنوان نفسها لا تتغيّر.
2O(n): خطّي
الزمن يتناسب طرديًا مع حجم المُدخل، مثل المرور على كل عناصر قائمة مرة واحدة. لو استغرق فحص عنصر واحد وحدة زمن واحدة، فحص 10 عناصر يستغرق 10 وحدات، و1000 عنصر يستغرق 1000 وحدة، العلاقة خط مستقيم تمامًا: ضاعف المُدخل فيتضاعف الزمن بنفس النسبة، لا أكثر ولا أقل.
3O(n²): تربيعي
الزمن يتناسب مع مربّع حجم المُدخل، شائع في خوارزميات الفرز البسيطة التي تقارن كل زوج من العناصر تقريبًا. الفرق هنا خطير عمليًا: مضاعفة حجم المُدخل في خوارزمية O(n) تضاعف الزمن مرة واحدة فقط، لكنها في خوارزمية O(n²) تضاعف الزمن أربع مرات (لأن (2n)² = 4n²)، وهذا تمامًا سبب كون Bubble Sort مقبولًا على 10 عناصر لكنه غير عملي بالكامل على مليون عنصر، حيث يصبح عدد المقارنات تقريبًا 500 مليار مقارنة بدل مليون فقط لخوارزمية خطّية.
مقارنة خوارزميات الفرز الشائعة
| الخوارزمية | أسوأ حالة | مستقرة؟ | في المكان (In-place)؟ | الفكرة |
|---|---|---|---|---|
| Bubble Sort | O(n²) | نعم | نعم | تبديل كل زوج متجاور غير مرتّب، وتكرار المرور حتى لا يحدث أي تبديل |
| Selection Sort | O(n²) | لا | نعم | إيجاد أصغر عنصر في الجزء غير المرتّب ووضعه في مكانه الصحيح، وتكرار ذلك |
| Insertion Sort | O(n²) | نعم | نعم | بناء الجزء المرتّب عنصرًا بعنصر، بإدخال كل عنصر جديد في مكانه الصحيح ضمنه |
| Merge Sort | O(n log n) | نعم | لا | تقسيم القائمة نصفين متكرر حتى عناصر مفردة، ثم دمجها مرتّبة تصاعديًا |
| Quick Sort | O(n²) (نادرًا) | لا | نعم | اختيار محور (Pivot) وتقسيم العناصر حوله، ثم الفرز التكراري لكل قسم |
شكل 2، Merge Sort يقسّم كل مستوى للنصف بالضبط فيحتاج log n مستوى فقط دائمًا؛ Quick Sort في أسوأ حالة يفصل عنصرًا واحدًا في كل مرة فيحتاج n مستوى كامل: هذا الفرق بالضبط هو سبب O(n log n) مقابل O(n²).
مثال محلول: تتبّع Bubble Sort خطوة بخطوة
فرز [5, 2, 4, 1] تصاعديًا:
| المرور | المقارنات والتبديلات | الحالة بعد المرور |
|---|---|---|
| 1 | 5>2 بدّل، 5>4 بدّل، 5>1 بدّل | [2, 4, 1, 5] |
| 2 | 2<4 لا تبديل، 4>1 بدّل | [2, 1, 4, 5] |
| 3 | 2>1 بدّل | [1, 2, 4, 5] ← لا تبديل بعدها، انتهى الفرز |
void bubble_sort(int *array, size_t size)
{
size_t i, j;
int swapped;
for (i = 0; i < size - 1; i++)
{
swapped = 0;
for (j = 0; j < size - i - 1; j++)
{
if (array[j] > array[j + 1])
{
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
swapped = 1;
}
}
if (!swapped) /* لا تبديل = القائمة مرتّبة، توقّف مبكرًا */
break;
}
}
لماذا هذا مهم فعليًا؟
🔎اختيار الأداة المناسبة
لمُدخل صغير جدًا أو شبه مرتّب مسبقًا، Insertion Sort البسيط فعليًا أسرع من Merge Sort الأكثر تعقيدًا؛ لمُدخل ضخم عشوائي، Merge Sort أو Quick Sort أفضل بكثير.
💬لغة مشتركة في المقابلات التقنية
Big O هي اللغة القياسية لمناقشة كفاءة أي حل برمجي، لا تحتاج لتشغيل الكود فعليًا لمقارنة حلّين نظريًا.
تعمّق: Big O والخوارزميات والاستقرار
الفرز مثال مثالي لتعلّم التفكير بالتعقيد: مسألة واحدة وعشرات الحلول التي تتفاوت آلاف المرات في السرعة. نشرح هنا فكرة كل خوارزمية بعيدًا عن الشيفرة، ثم نحدد الفرق بين الفرز المستقر وغير المستقر، وكيف نختار.
أولًا: لغة Big O بالأرقام
Big O لا يقيس ثواني بل كيف ينمو العمل مع حجم المدخل n، متجاهلًا الثوابت والحدود الصغيرة. ولذلك فـ3n + 10 هو O(n) و n² + n هو O(n²). والجدول التالي يوضّح لماذا يهم الفرق، بعدد العمليات التقريبي:
| الصنف | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| O(1) | 1 | 1 | 1 |
| O(log n) | ≈ 3 | ≈ 10 | ≈ 20 |
| O(n) | 10 | 1,000 | 1,000,000 |
| O(n log n) | ≈ 33 | ≈ 10,000 | ≈ 20,000,000 |
| O(n²) | 100 | 1,000,000 | 1,000,000,000,000 |
انظر إلى الصف الأخير: بمليون عنصر تحتاج خوارزمية تربيعية إلى تريليون عملية، أي ساعات، بينما تحتاج خوارزمية n log n إلى عشرين مليونًا فقط، أي أجزاء من الثانية. هذا ما يجعل اختيار الخوارزمية أهم من تحسين الشيفرة سطرًا بسطر.
ثانيًا: فكرة كل خوارزمية
🫧الفقاعة (Bubble)
تقارن كل جارين متجاورين وتبدّلهما إن كانا في ترتيب خاطئ، فتطفو القيمة الأكبر إلى النهاية في كل مرور. تكرر المرور حتى لا يحدث تبديل. بسيطة لكنها O(n²) إلا إن كانت المدخلات شبه مرتبة وكشفت المرور بلا تبديل.
🃏الإدراج (Insertion)
كمن يرتب أوراق اللعب في يده: يأخذ العنصر التالي ويُدخله في موضعه الصحيح بين المرتَّب منها. ممتازة للمدخلات الصغيرة أو شبه المرتبة (O(n) في أفضل حالاتها).
🎯الاختيار (Selection)
تجد أصغر عنصر في الجزء غير المرتب وتضعه في أول موضع غير مرتب. تجري عددًا قليلًا من التبديلات لكنها دائمًا O(n²) في المقارنات مهما كان المدخل.
⚡السريع (Quick)
تختار عنصرًا محوريًا (Pivot) وتقسم المصفوفة إلى ما هو أصغر منه وما هو أكبر، ثم تفرز كل جزء بالطريقة نفسها. متوسطها O(n log n) وهي سريعة عمليًا، لكن اختيار محور سيئ باستمرار (مثلًا أصغر عنصر في مصفوفة مرتبة) يوصلها إلى O(n²).
شكل 3، فكرة الفرز السريع: قسّم حول المحور ثم عالج كل جزء.
ثالثًا: الفرز المستقر
الفرز المستقر يحافظ على الترتيب الأصلي للعناصر ذات المفتاح المتساوي. مثال: لديك طلاب مرتّبين بالاسم وتفرزهم بالدرجة. في الفرز المستقر يبقى الطلاب ذوو الدرجة نفسها بترتيب الاسم، أما في غير المستقر فقد يختلط ترتيبهم. وهذا يهم حين تفرز بمفتاحين متتاليين: فرز مستقر بالمفتاح الثانوي ثم بالرئيسي يعطي ترتيبًا صحيحًا. الفقاعة والإدراج مستقرتان، بينما الاختيار والسريع في أبسط صورهما غير مستقرتين.
| الترتيب | السجلات (الاسم، الدرجة) |
|---|---|
| قبل الفرز (مرتبة بالاسم) | Ali B, Dana A, Omar A, Sara B |
| بعد فرز مستقر بالدرجة | Dana A, Omar A, Ali B, Sara B |
| بعد فرز غير مستقر (نتيجة ممكنة) | Omar A, Dana A, Sara B, Ali B |
كلا الترتيبين مرتب بالدرجة، لكن المستقر وحده يُبقي Dana قبل Omar و Ali قبل Sara كما في الأصل.
رابعًا: كيف تختار الخوارزمية؟
| الخوارزمية | أفضل | متوسط | أسوأ | ذاكرة إضافية | مستقرة |
|---|---|---|---|---|---|
| الفقاعة | O(n) | O(n²) | O(n²) | O(1) | نعم |
| الإدراج | O(n) | O(n²) | O(n²) | O(1) | نعم |
| الاختيار | O(n²) | O(n²) | O(n²) | O(1) | لا |
| السريع | O(n log n) | O(n log n) | O(n²) | O(log n) | لا |
| الدمج | O(n log n) | O(n log n) | O(n log n) | O(n) | نعم |
شكل 4، شجرة قرار مبسطة لاختيار الفرز بحسب خصائص المدخل.
الحكم على الخوارزمية بتجربة واحدة على مدخل صغير. O(n²) قد تتفوق على O(n log n) عند n صغير بسبب ثوابتها الصغيرة، ولذلك لا تعمّم إلا بعد قياس على أحجام مختلفة وبيانات متنوعة (مرتبة، معكوسة، عشوائية).
جرّب بنفسك
ماذا تقيس Big O؟
الثواني تعتمد على الجهاز؛ Big O تصف سلوك النمو، وعادة في أسوأ الحالات.
إن ضاعفت حجم المُدخل في خوارزمية O(n²) فإن الزمن تقريبًا:
الزمن يتناسب مع مربّع n؛ المضاعفة تعطي 2² = 4 أضعاف.
أي خوارزمية فرز ممتازة للمُدخلات الصغيرة أو شبه المرتبة (O(n) في أفضل حالاتها)؟
الإدراج يُدخل كل عنصر في موضعه بين المرتّب، فيكاد لا يتحرّك شيء في مُدخل شبه مرتّب.
بطاقات مراجعة سريعة
تحقق من فهمك
لماذا يوقف كود Bubble Sort أعلاه التنفيذ مبكرًا (break) لو لم يحدث أي تبديل في مرور كامل؟
لأن عدم حدوث أي تبديل يعني أن القائمة أصبحت مرتّبة بالكامل بالفعل، الاستمرار بمرورات إضافية سيكون عملًا مهدرًا دون أي فائدة.
لو كان لديك مُدخل صغير جدًا (5 عناصر فقط)، هل يستحق استخدام Merge Sort المعقّد بدل Bubble Sort البسيط؟
غالبًا لا، الفرق العملي في الأداء على مُدخل بهذا الصغر ضئيل جدًا، بينما التعقيد الإضافي في الكود (تقسيم، دمج، ذاكرة إضافية) لا يبرَّر إلا عند أحجام مُدخل أكبر بكثير.
لديك مصفوفة شبه مرتبة وصغيرة، أي خوارزمية تختار؟
الإدراج: تقترب من O(n) وهي مستقرة وبسيطة.
كم عملية تقريبية يحتاجها O(n²) لمليون عنصر؟
نحو تريليون عملية.
مصادر هذا الدرس
مرتّبة بالنوع. ابدأ بالتوثيق الرسمي إذا تبي المرجع الدقيق، وبالمقال أو الفيديو إذا تبي الشرح أولًا.
أدوات2
خلّصت الدرس؟
سجّل الدخول ليُحفظ تقدّمك.