كلفة الخوارزمية

عدّ العمليات

السؤال الثاني

علّم الدرسان تصميم حلقات صحيحة والاستدعاء الذاتي كيف نبرهن أن خوارزمية صحيحة: أنها تنتهي وأن نتيجتها تحقق الشرط اللاحق. غير أن الدرس الخوارزميات العددية عرض اختبارين للأولية صحيحين بالقدر نفسه، أحدهما بنحو $n$ قسمة والآخر بنحو $\sqrt{n}$، وعرض الدرس الاستدعاء الذاتي طريقتين صحيحتين لحساب $F_{30}$، إحداهما بـ $2\,692\,537$ استدعاءً والأخرى بـ 29 عملية جمع. وإذا كان الأمر كذلك، فالصحة لا تكفي للاختيار: فمن بين خوارزميتين صحيحتين، قد تجيب إحداهما في لحظة ولا تنتهي الأخرى قبل أن تفقد الإجابة أهميتها. فالسؤال الثاني الذي يُطرح على خوارزمية هو إذن: كم تكلّف.

كان يمكن قياس الكلفة بساعة، وسيفعل ذلك القسم الرابع. لكن زمن تنفيذ واحد يتوقف على الجهاز، وعلى المترجم، وعلى خياراته، وعلى ما يفعله الحاسوب في الوقت نفسه؛ ولا يلزم عنه شيء عن الخوارزمية على جهاز آخر. أما ما لا يتوقف على شيء من ذلك فهو عدد الخطوات التي تخطوها الخوارزمية. ومن ذلك يلزم القرار الأول في هذا الدرس: أن نقيس الكلفة بالعدّ، وأن نترك الساعة للتحقق من العدّ.

الحجم والعملية المهيمنة

عدّ كل الخطوات (كل جمع، وكل مقارنة، وكل زيادة للفهرس، وكل وصول إلى الذاكرة) سيكون مملًّا وعديم الجدوى، لأن جلّها يصاحب خطوة رئيسية بنسبة ثابتة. فنختار إذن العملية المهيمنة: وهي التي تُنفَّذ مرات لا تقلّ عن مرات أي عملية أخرى، إلا بعامل ثابت، ولذلك تمثّلها جميعًا. ففي مجموع عناصر متجه هي الجمع؛ وفي البحث عن قيمة عظمى هي المقارنة؛ وفي اختبار الأولية هي القسمة. ويُعبَّر عن عدد مرات تنفيذها بدلالة حجم المدخلات، الذي يُسمّى $n$: عدد عناصر المتجه، أو العدد الذي يُختبر، أو عدد الأرقام.

الحلقة البسيطة التي تمرّ على متجه من $n$ عنصرًا وتؤدي مع كل عنصر مقدارًا ثابتًا من العمل تنفّذ عمليتها المهيمنة $n$ مرة. أما القيمة العظمى لمتجه غير فارغ، فتبدأ بالعنصر الأول مرشّحًا وتقارن به كل عنصر من البقية: $n - 1$ مقارنة. والفرق بين $n$ و$n - 1$ حقيقي، لكنه، كما سيظهر في القسم الثالث، لا يغيّر شيئًا مما يهمّ.

أسوأ حالة

بعض الخوارزميات لا تنفّذ دائمًا العدد نفسه من العمليات مع بيانات من الحجم نفسه. فالبحث عن قيمة في متجه، بالمرور عليه حتى العثور عليها، يُجري مقارنة واحدة إن كانت القيمة في الموضع الأول و$n$ مقارنة إن لم تكن فيه. وللحديث عن كلفته نختار إحدى الحالتين، والاختيار المعتاد هو أسوأ حالة: أكبر عدد من العمليات بين كل المدخلات التي حجمها $n$. والسبب هو نفسه الذي يجعل العقد يُكتب لكل المدخلات التي تحقق الشرط المسبق: أسوأ حالة ضمان، وأفضل حالة أمل. وهكذا يكلّف البحث الخطي $n$ مقارنة في أسوأ حالة، وحين يقول هذا الدرس «الكلفة» من غير قيد، فإنه يعني كلفة أسوأ حالة.

الحلقات المتداخلة

علّم الدرس الحلقات عدّ جولات حلقتين متداخلتين. فإن كانت الداخلية تؤدي دائمًا $m$ جولة عن كل جولة من جولات الخارجية البالغة $n$، نُفِّذ الجسم الداخلي $n \cdot m$ مرة. وإن كانت الداخلية تتوقف على الخارجية، جُمِعت الجولات صفًّا صفًّا. والحالة الأكثر ظهورًا عند العمل مع المجموعات هي حالة كل الأزواج: مقارنة كل عنصر بكل عنصر يليه، كما عند البحث هل في متجه عناصر مكررة.

#include <print>​int main(){    for (int n{10}; n <= 10'000; n *= 10) {        long long comparisons{0};        for (int i{0}; i < n; ++i) {            for (int j{i + 1}; j < n; ++j) {                ++comparisons;            }        }        std::println("n = {:>6}: {:>10} مقارنة؛ n(n - 1)/2 = {}",                     n, comparisons, static_cast<long long>(n) * (n - 1) / 2);    }}

n =     10:         45 مقارنة؛ n(n - 1)/2 = 45n =    100:       4950 مقارنة؛ n(n - 1)/2 = 4950n =   1000:     499500 مقارنة؛ n(n - 1)/2 = 499500n =  10000:   49995000 مقارنة؛ n(n - 1)/2 = 49995000

يحلّ العدّاد محلّ المقارنة التي كانت الخوارزمية الحقيقية ستجريها. ففي الجولة $i$ من الخارجية، تمتد الداخلية من $i + 1$ إلى $n - 1$ وتؤدي $n - 1 - i$ جولة؛ فيكون المجموع $(n - 1) + (n - 2) + \cdots + 1 + 0$، وهو مجموع الدرس الحلقات:

تؤكد المخرجات الصيغة لكل حجم. والعدّاد من النوع long long لأنه ابتداءً من $n$ يقارب خمسة وستين ألفًا يتجاوز عدد الأزواج الحدَّ الأقصى لـ int (ذي 32 بتًا في هذه المنصة)، والصيغة تضرب بعد التحويل للسبب نفسه: عدّاد الخوارزمية التربيعية يفيض قبل البيانات بكثير.

ولنلاحظ منذ الآن ما سيعمّمه القسم الثالث: عند ضرب $n$ في 10، تُضرب المقارنات في 100 تقريبًا. فمع عشرة بيانات، 45 مقارنة؛ ومع عشرة آلاف، قرابة خمسين مليونًا.