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

في علم الحاسوب ، تُعدّ الكفاءة الخوارزمية خاصيةً للخوارزمية تتعلق بكمية الموارد الحاسوبية التي تستخدمها. ويمكن تشبيه الكفاءة الخوارزمية بإنتاجية الهندسة في العمليات المتكررة أو المستمرة.

لتحقيق أقصى قدر من الكفاءة، يُفضّل تقليل استخدام الموارد. مع ذلك، لا يمكن مقارنة الموارد المختلفة، مثل تعقيد الوقت والمساحة ، بشكل مباشر، لذا فإن تحديد أي من الخوارزميتين أكثر كفاءة يعتمد غالبًا على معيار الكفاءة الأكثر أهمية.

على سبيل المثال، تُعدّ كل من خوارزمية فرز الدورة وخوارزمية فرز الوقت خوارزميتين لفرز قائمة من العناصر من الأصغر إلى الأكبر. تُنظّم خوارزمية فرز الدورة القائمة في وقت يتناسب مع مربع عدد العناصر (${\textstyle O(n^{2})}$(انظر ترميز Big O )، ولكنه يقلل من عمليات الكتابة إلى المصفوفة الأصلية ولا يتطلب سوى مقدار صغير من الذاكرة الإضافية التي تكون ثابتة بالنسبة لطول القائمة (${\textstyle O(1)}$تقوم خوارزمية Timsort بترتيب القائمة في وقت خطي لوغاريتمي (يتناسب مع كمية مضروبة في لوغاريتمها) حسب طول القائمة.${\textstyle O(n\log n)}$)، لكن متطلبات المساحة فيه خطية بالنسبة لطول القائمة (${\textstyle O(n)}$). إذا كان يجب فرز القوائم الكبيرة بسرعة عالية لتطبيق معين، فإن خوارزمية timsort هي الخيار الأفضل؛ ومع ذلك، إذا كان تقليل دورات البرنامج/المسح  وبصمة الذاكرة للفرز أكثر أهمية، فإن خوارزمية cycle sort هي الخيار الأفضل.

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

"في كل عملية حسابية تقريباً، توجد مجموعة متنوعة من الترتيبات الممكنة لتتابع العمليات، ويجب أن تؤثر اعتبارات مختلفة على الاختيارات من بينها لأغراض محرك الحساب. أحد الأهداف الأساسية هو اختيار الترتيب الذي من شأنه أن يقلل إلى الحد الأدنى من الوقت اللازم لإكمال الحساب" ^{[ 1 ]}

كانت الحواسيب الإلكترونية المبكرة محدودة السرعة وذاكرة الوصول العشوائي . ولذلك، كان لا بد من المفاضلة بين المساحة والوقت . إذ كان بالإمكان استخدام خوارزمية سريعة تستهلك ذاكرة كبيرة، أو خوارزمية بطيئة تستهلك ذاكرة صغيرة. ولذا، تمثلت المفاضلة الهندسية في استخدام أسرع خوارزمية تتناسب مع الذاكرة المتاحة.

تتميز الحواسيب الحديثة بسرعتها الفائقة مقارنةً بالحواسيب القديمة، كما أنها تتمتع بسعة ذاكرة أكبر بكثير ( جيجابايت بدلاً من كيلوبايت ). ومع ذلك، أكد دونالد كنوث على أن الكفاءة لا تزال عاملاً مهماً.

"في التخصصات الهندسية الراسخة، لا يعتبر التحسن بنسبة 12٪، والذي يمكن تحقيقه بسهولة، هامشيًا أبدًا، وأعتقد أن وجهة النظر نفسها يجب أن تسود في هندسة البرمجيات" ^{[ 2 ].}

في عصر الذكاء الاصطناعي ، في حين أن نماذج التعلم الآلي يمكن أن تولد رمزًا يعمل، إلا أن هذه النماذج غالبًا ما تقصر عن معايير الأداء المطلوبة في التطبيقات ذات الموارد المحدودة أو الحساسة للوقت ^{[ 3 ]} ، مما يجعل كفاءة الكود عنق زجاجة حاسمًا للنشر في العالم الحقيقي.

تُعتبر الخوارزمية فعّالة إذا كان استهلاكها للموارد، المعروف أيضًا بالتكلفة الحسابية، عند مستوى مقبول أو أقل منه. وبشكل عام، يُقصد بـ"المقبول" أنها ستعمل في وقت أو مساحة معقولة على جهاز حاسوب متاح، وعادةً ما يكون ذلك مرتبطًا بحجم المدخلات. منذ خمسينيات القرن الماضي، شهدت أجهزة الحاسوب زيادات هائلة في كلٍ من القدرة الحسابية المتاحة وسعة الذاكرة، لذا فإن المستويات المقبولة الحالية كانت غير مقبولة حتى قبل عشر سنوات. في الواقع، بفضل تضاعف قدرة الحوسبة تقريبًا كل عامين ، فإن المهام التي تُعتبر فعّالة بشكل مقبول على الهواتف الذكية الحديثة والأنظمة المدمجة ربما كانت غير فعّالة بشكل غير مقبول على الخوادم الصناعية قبل عشر سنوات.

تُصدر شركات تصنيع الحواسيب باستمرار طرازات جديدة، غالباً ما تتميز بأداء أعلى . قد تكون تكاليف البرامج مرتفعة للغاية، لذا في بعض الحالات، قد يكون شراء حاسوب أسرع هو أبسط وأرخص طريقة للحصول على أداء أفضل، شريطة أن يكون متوافقاً مع الحاسوب الحالي.

تتعدد طرق قياس الموارد التي يستخدمها أي خوارزمية: وأكثرها شيوعًا السرعة واستخدام الذاكرة؛ وتشمل المقاييس الأخرى سرعة النقل، واستخدام القرص المؤقت، واستخدام القرص طويل الأمد، واستهلاك الطاقة، والتكلفة الإجمالية للملكية ، وزمن الاستجابة للمؤثرات الخارجية، وغيرها. يعتمد الكثير من هذه المقاييس على حجم مدخلات الخوارزمية، أي كمية البيانات المراد معالجتها. وقد يعتمد أيضًا على طريقة ترتيب البيانات؛ فعلى سبيل المثال، قد يكون أداء بعض خوارزميات الفرز ضعيفًا على البيانات المرتبة مسبقًا، أو المرتبة بترتيب عكسي.

عمليًا، توجد عوامل أخرى قد تؤثر على كفاءة الخوارزمية، مثل متطلبات الدقة و/أو الموثوقية. وكما هو موضح أدناه، فإن طريقة تنفيذ الخوارزمية قد يكون لها تأثير كبير على الكفاءة الفعلية، على الرغم من أن العديد من جوانب ذلك تتعلق بقضايا التحسين .

التحليل النظري

في التحليل النظري للخوارزميات ، تتمثل الممارسة المعتادة في تقدير تعقيدها بالمعنى التقاربي. وأكثر الرموز استخدامًا لوصف استهلاك الموارد أو "التعقيد" هو رمز Big O لدونالد كنوث ، الذي يمثل تعقيد الخوارزمية كدالة لحجم المدخلات.${\textstyle n}$يُعدّ ترميز Big O مقياسًا تقاربيًا لتعقيد الدالة، حيث${\textstyle f(n)=O{\bigl (}g(n){\bigr )}}$يعني ذلك تقريبًا أن الوقت اللازم لتنفيذ خوارزمية ما يتناسب مع${\displaystyle g(n)}$مع حذف الحدود ذات الرتبة الأدنى التي تساهم بأقل من${\displaystyle g(n)}$لنمو الوظيفة كـ${\textstyle n}$ينمو بشكل كبير بشكل تعسفي . قد يكون هذا التقدير مضللاً عندما${\textstyle n}$صغير الحجم، ولكنه دقيق بشكل عام عندما${\textstyle n}$تكون القيمة كبيرة لأن الترميز تقاربي. على سبيل المثال، قد يكون فرز الفقاعات أسرع من فرز الدمج عند فرز عدد قليل من العناصر؛ ومع ذلك، من المرجح أن يلبي أي من التنفيذين متطلبات الأداء لقائمة صغيرة. عادةً، يهتم المبرمجون بالخوارزميات التي تتوسع بكفاءة لأحجام إدخال كبيرة، ويُفضل فرز الدمج على فرز الفقاعات للقوائم ذات الطول الذي يُصادف في معظم البرامج كثيفة البيانات.

تتضمن بعض الأمثلة على استخدام ترميز Big O في حساب التعقيد الزمني التقاربي للخوارزميات ما يلي:

الترميز	اسم	أمثلة
${\displaystyle O(1)}$	ثابت	إيجاد الوسيط من قائمة مرتبة من القياسات؛ استخدام جدول بحث ذي حجم ثابت ؛ استخدام دالة تجزئة مناسبة للبحث عن عنصر.
${\displaystyle O(\log n)}$	اللوغاريتمي	إيجاد عنصر في مصفوفة مرتبة باستخدام البحث الثنائي أو شجرة البحث المتوازنة بالإضافة إلى جميع العمليات في كومة ذات الحدين .
${\displaystyle O(n)}$	خطي	إيجاد عنصر في قائمة غير مرتبة أو شجرة مشوهة (أسوأ حالة) أو في مصفوفة غير مرتبة؛ جمع عددين صحيحين من n بت عن طريق الحمل المتتالي .
${\displaystyle O(n\log n)}$	خطي لوغاريتمي ، أو لوغاريتمي خطي، أو شبه خطي	إجراء تحويل فورييه السريع ؛ فرز الكومة ، أو الفرز السريع ( في أفضل حالة ومتوسطها )، أو فرز الدمج
${\displaystyle O(n^{2})}$	التربيعي	ضرب عددين مكونين من n خانة باستخدام خوارزمية بسيطة ؛ فرز الفقاعات (أسوأ حالة أو تطبيق بسيط)، فرز شل ، الفرز السريع ( أسوأ حالة )، فرز التحديد أو فرز الإدراج
${\displaystyle O(c^{n}),\;c>1}$	النمو الأسي	إيجاد الحل الأمثل (غير التقريبي ) لمسألة البائع المتجول باستخدام البرمجة الديناميكية ؛ وتحديد ما إذا كانت عبارتان منطقيتان متكافئتين باستخدام البحث الشامل.

تُعبّر المقاييس عادةً عن نفسها كدالة لحجم المدخلات.${\displaystyle \scriptstyle {n}}$.

الإجراءان الأكثر شيوعاً هما:

• الوقت : كم من الوقت تستغرقه الخوارزمية لإكمالها؟
• المساحة : ما مقدار ذاكرة العمل (عادةً ذاكرة الوصول العشوائي) التي تحتاجها الخوارزمية؟ وهذا له جانبان: مقدار الذاكرة التي يحتاجها الكود (استخدام المساحة المساعدة)، ومقدار الذاكرة اللازمة للبيانات التي يعمل عليها الكود (استخدام المساحة الجوهرية).

بالنسبة لأجهزة الكمبيوتر التي يتم تزويدها بالطاقة بواسطة بطارية (مثل أجهزة الكمبيوتر المحمولة والهواتف الذكية )، أو لإجراء حسابات طويلة/كبيرة جدًا (مثل أجهزة الكمبيوتر العملاقة )، ​​فإن المقاييس الأخرى ذات الأهمية هي:

• استهلاك الطاقة المباشر : الطاقة اللازمة لتشغيل الكمبيوتر بشكل مباشر.
• استهلاك الطاقة غير المباشر : الطاقة اللازمة للتبريد والإضاءة وما إلى ذلك.

اعتبارًا من عام 2018يتزايد استهلاك الطاقة كمقياس مهم للمهام الحسابية بجميع أنواعها وعلى جميع المستويات، بدءًا من أجهزة إنترنت الأشياء المدمجة وصولًا إلى أنظمة على شريحة واحدة ومزارع الخوادم . ويُشار إلى هذا التوجه غالبًا باسم الحوسبة الخضراء .

قد تكون مقاييس الكفاءة الحسابية الأقل شيوعًا ذات صلة في بعض الحالات:

• حجم الإرسال : قد يُمثل عرض النطاق الترددي عاملاً مُحدداً. يُمكن استخدام ضغط البيانات لتقليل حجم البيانات المُرسلة. على سبيل المثال، قد يؤدي عرض صورة (مثل شعار جوجل ) إلى إرسال عشرات الآلاف من البايتات (48 كيلوبايت في هذه الحالة) مقارنةً بإرسال ستة بايتات فقط لنص "جوجل". يُعد هذا الأمر بالغ الأهمية لمهام الحوسبة التي تعتمد على عمليات الإدخال والإخراج .
• المساحة الخارجية : المساحة المطلوبة على القرص أو جهاز ذاكرة خارجي آخر؛ يمكن أن يكون ذلك للتخزين المؤقت أثناء تنفيذ الخوارزمية، أو يمكن أن يكون تخزينًا طويل الأجل مطلوبًا لنقله للرجوع إليه في المستقبل.
• زمن الاستجابة ( زمن الكمون ): هذا الأمر ذو أهمية خاصة في التطبيقات التي تعمل في الوقت الحقيقي عندما يتعين على نظام الكمبيوتر الاستجابة بسرعة لبعض الأحداث الخارجية .
• التكلفة الإجمالية للملكية : خاصة إذا كان جهاز الكمبيوتر مخصصًا لخوارزمية معينة.

• تحليل الخوارزميات - كيفية تحديد الموارد التي تحتاجها الخوارزمية.
• المعيار المرجعي — طريقة لقياس وقت التنفيذ والمساحة المستخدمة في حالات محددة. ^{[ 10 ] [ 11 ] [ 12 ]}
• أفضل الحالات وأسوأها ومتوسطها - اعتبارات لتقدير أوقات التنفيذ في ثلاثة سيناريوهات.
• تحسين المُترجم — التحسين المُستمد من المُترجم.
• نظرية التعقيد الحسابي
• أداء الحاسوب — مقاييس أجهزة الحاسوب.
• علم الخوارزميات التجريبي - ممارسة استخدام الأساليب التجريبية لدراسة سلوك الخوارزميات.
• مخطط الخوارزميات
• تحسين البرنامج
• تحليل الأداء - طرق قياس الأداء الفعلي للخوارزمية في وقت التشغيل.