ما معنى صيغة ستيرلينغ (Stirling's Formula) في الخوارزميات وهياكل البيانات؟
صيغة ستيرلينغ (Stirling's Formula) في سياق الخوارزميات وهياكل البيانات هي تقريبٌ رياضي يقدّر قيمة العاملي n! عندما يكون العدد n كبيرًا، من دون الحاجة إلى ضرب الأعداد واحدًا تلو الآخر. صيغتها المختصرة هي:
n! ≈ √(2πn) × (n/e)ⁿ
لكن الفائدة الحقيقية لمهندس البرمجيات ليست في حساب n! نفسه، بل في لوغاريتمه: فصيغة ستيرلينغ تُخبرنا أن log(n!) يساوي تقريبًا n·log(n). وهذه بالضبط هي الحلقة التي تفسّر لماذا لا تستطيع أي خوارزمية فرز تعتمد على المقارنة أن تكون أسرع من n·log(n). إن لم تكن قد رأيت الرابط بين العاملي وخوارزميات الفرز من قبل، فهذا المقال يوصلك إليه خطوة بخطوة.
الصيغة نفسها ومعناها البديهي
العاملي n! = 1 × 2 × 3 × … × n ينمو بسرعة مرعبة؛ فـ 20! وحده يقارب 2.4 × 10¹⁸. حساب هذا العدد بالضرب المباشر ممكن، لكن تحليله رياضيًا (مثل معرفة عدد خاناته أو مقارنته بدوال أخرى) يصبح صعبًا. هنا تدخل صيغة ستيرلينغ: تحوّل حاصل ضرب طويلًا إلى تعبير مغلق يعتمد على القوى والجذور فقط.
بديهيًا، العاملي يقع «بين» الأس الخالص (eⁿ) وبين nⁿ، وصيغة ستيرلينغ تحدد موقعه الدقيق: n! يتصرف مثل (n/e)ⁿ مضروبًا في عامل تصحيح صغير √(2πn). كلما كبر n، ازدادت دقة التقريب.
المفتاح الحقيقي: لوغاريتم العاملي
في تحليل الخوارزميات نادرًا ما نهتم بالقيمة الدقيقة لـ n!، بل بمعدّل نموّها ضمن الترميز المقارب (Big-O). لذلك نأخذ اللوغاريتم لطرفي الصيغة:
log₂(n!) ≈ n·log₂(n) − 1.4427·n + ½·log₂(2πn)
الحدّ المهيمن هنا هو n·log₂(n)، أما البقية فتُهمَل في الترميز المقارب. الخلاصة التي نستخدمها في كل مكان تقريبًا:
log(n!) = Θ(n log n)
هذه المعادلة القصيرة هي جوهر مساهمة ستيرلينغ في علوم الحاسب. من دونها كان من الصعب إثبات كثير من الحدود الدنيا (lower bounds).
التطبيق الأشهر: لماذا لا يمكن الفرز أسرع من n log n؟
هذا هو المثال الذي يجعل ستيرلينغ لا غنى عنها في مقرر هياكل البيانات:
- أي خوارزمية فرز تعتمد على مقارنة العناصر (مثل QuickSort وMergeSort وHeapSort) يمكن تمثيلها بشجرة قرار، كل ورقة فيها تمثّل ترتيبًا نهائيًا ممكنًا.
- عدد الترتيبات الممكنة لـ n عنصرًا هو n!، أي أن الشجرة يجب أن تحوي n! ورقة على الأقل.
- شجرة ثنائية بارتفاع h لا تحوي أكثر من 2ʰ ورقة، إذًا: 2ʰ ≥ n!، ومنه h ≥ log₂(n!).
- بتطبيق ستيرلينغ: log₂(n!) ≈ n·log₂(n)، فيكون الارتفاع (وهو أسوأ عدد مقارنات) لا يقل عن Ω(n log n).
النتيجة: لا يمكن لأي فرز قائم على المقارنة أن يكسر حاجز n·log(n) في الحالة الأسوأ. هذا الإثبات النظري يعتمد كليًا على تقريب ستيرلينغ، وهو السبب الأول لظهورها في المنهج.
معامِلات ذات الحدّين والمعامل المركزي
تطبيق مهم آخر يخص معاملات ذات الحدّين C(n, k) = n! / (k!·(n−k)!). عند تحليل الخوارزميات الاحتمالية والتوافقية، نحتاج غالبًا لتقدير المعامل المركزي C(2n, n)، وبتطبيق ستيرلينغ نحصل على تقريب أنيق:
C(2n, n) ≈ 4ⁿ / √(πn)
يظهر هذا التقدير في تحليل أعداد كتالان (Catalan numbers)، وفي حساب عدد الأشجار الثنائية الممكنة، وفي براهين الاحتمالات. إنه المكان الثاني الذي تلمس فيه ستيرلينغ فعليًا داخل هياكل البيانات.
ما مدى دقة التقريب؟
من المفيد أن ترى بعينك كم يقترب تقريب ستيرلينغ من القيمة الحقيقية، وكيف يتحسّن مع كبر n:
| n | القيمة الفعلية n! | تقريب ستيرلينغ | نسبة الخطأ |
|---|---|---|---|
| 1 | 1 | 0.92 | 7.8% |
| 5 | 120 | 118.0 | 1.65% |
| 10 | 3,628,800 | 3,598,696 | 0.83% |
| 15 | 1,307,674,368,000 | ≈1.3004 × 10¹² | 0.55% |
| 20 | ≈2.4329 × 10¹⁸ | ≈2.4228 × 10¹⁸ | 0.42% |
لاحظ أن الخطأ النسبي يتناقص باطّراد كلما كبر n، وهذا بالضبط سبب قولنا إن الصيغة «تقريب للقيم الكبيرة». التقريب دائمًا أقل قليلًا من القيمة الحقيقية.
خطأ شائع يجب تجنّبه
الصفحات الضعيفة كثيرًا ما توحي بأن ستيرلينغ «أداة سحرية» تُستخدم في كل شيء: جداول التجزئة (Hash Tables)، وتقدير التصادمات، وتحسين الأشجار… هذا مبالغة مضللة. في الممارسة العملية، حسابات جداول التجزئة تعتمد على نماذج الاحتمالات وعامل التحميل، لا على تقريب العاملي مباشرة. الدور الأصيل والدقيق لستيرلينغ محصور في أمرين: تقدير log(n!) لإثبات الحدود الدنيا، وتقدير معاملات ذات الحدّين. اعرف حدودها لتستخدمها في مكانها الصحيح.
خطأ آخر: بعض الطلاب يحفظون الصيغة بصورة n! ≈ (n/e)ⁿ ناسين عامل √(2πn). من دون هذا العامل يصبح التقريب رديئًا للقيم الصغيرة والمتوسطة، ويعطي خطأً أكبر بكثير.
الأسئلة الشائعة
هل أحتاج حفظ صيغة ستيرلينغ لاجتياز مقرر الخوارزميات؟ يكفي أن تحفظ نتيجتها المقاربة log(n!) = Θ(n log n)، فهي التي تُستخدم في البراهين. أما الصيغة الكاملة بعامل √(2πn) فتُطلب عادةً في المسائل الرياضية أو التوافقية الدقيقة.
ما الفرق بين استخدامها في الرياضيات وفي علوم الحاسب؟ في الرياضيات يهمّنا الحصول على قيمة عددية تقريبية دقيقة لـ n!. أما في علوم الحاسب فيهمّنا سلوكها المقارب عبر اللوغاريتم، لأننا نحلّل معدلات النمو لا القيم المطلقة.
هل هي دقيقة للأعداد الصغيرة مثل n = 3؟ دقتها متواضعة عند القيم الصغيرة (الخطأ قد يتجاوز 5%)، وتتحسن سريعًا مع كبر n. لهذا تُسمّى تقريبًا مقاربًا (asymptotic) صالحًا للأعداد الكبيرة.
هل ترتبط ستيرلينغ بخوارزميات الفرز غير المعتمدة على المقارنة؟ لا مباشرة. خوارزميات مثل Counting Sort وRadix Sort تتجاوز حاجز n log n لأنها لا تقارن العناصر، وبالتالي لا ينطبق عليها برهان شجرة القرار المبني على n!.