مرجع
آخر الزيارات

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

583 كلمة•0 مشاهدة•🗒️ منذ يوم
باختصار: تُعرّف الكفاءة الخوارزميّة في علم الحاسوب بأنها إحدى خصائص الخوارزميات التي تتعلق بعدد الموارد الحاسوبية (الوقت، السرعة، الذاكرة..) التي تستعملها الخوارزمية أثناء عملها، وهنا يجب أن يتم تحليل الخوارزمية لتحديد مدى استخدامها للموارد وتحديد…. في هذه المقالة 6 أقسام: «التحليل النظري»، «المساحة» و«نظريًا» وغيرها.
المحتويات
  1. التحليل النظري
  2. المساحة
  3. نظريًا
  4. حجم الذاكرة للبيانات المُدخلة
  5. نظرة عامة
  6. مقياس استخدام الموارد

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

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

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

وفي هذا السياق، يمكن تحليل الخوارزمية نظريًا من خلال حساب تعقيد الخوارزمية باستخدام رمز O الكبير، حيث يرمز إلى مدى تعقيد الخوارزمية كاقتران مرتبط بحجم البيانات.

وفي هذا السياق، و يعتبر هذا المقياس دقيق بشكل معقول إذا كان حجم البيانات كبير، ولكن لا يمكن أخذه بعين الاعتبار على البيانات القليلة.

المساحة

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

حجم الذاكرة التي تحتاجها الشيفرة البرمجية للخوارزمية

هناك أربع جوانب لاستخدام الذاكرة يجب التنبه لها:

نظريًا

ومن ناحية أخرى، يُستعمل التعقيد الزمني لتحليل الوقت الذي تستعمله الخوارزمية بالنسبة لكمية المدخلات.

من جهة ثانية، النتيجة يمكن التعبير عنها بواسطة  رمز O الكبير. يمكن من خلال هذه العملية مقارنة الخوارزميات خاصة إذا كان لدينا كم كبير من البيانات لمعالجتها.

حجم الذاكرة للبيانات المُدخلة

علاوةً على ذلك، حجم الذاكرة للبيانات المخرجة (بعض الخوارزميات مثل خوارزميات الترتيب لا تحتاج إلى مخرجات)

علاوةً على ذلك، الخوارزمية التي تحتاج ذاكرة تتناسب مع مساحة الذاكرة المخبئية Cache Memory سيكون أداؤها أفضل بمراحل من الخوارزمية التي تحتاج إلى سعة الذاكرة الرئيسة، وبدورها ستكون أسرع بكثير من الخوارزمية التي تحتاج إلى الذاكرة الافتراضية.

حجم الذاكرة التي تحتاجها الخوارزمية للحسابات أثناء عملها.

ومن ناحية أخرى، الذاكرة المخبئية Cache Memory – وهذه تعمل بسرعة عالية جداً متناسبة مع وحدة المعالجة المركزية.

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

ومن جهة أخرى، الذاكرة الافتراضية – وهذه توحي للمستعمل بأن هناك مساحة كبيرة من الذاكرة، لكن أبطأ بآلاف المرات من الذاكرة العشوائية.

من جانب آخر، الذاكرة الفيزيائية الرئيسة، وهذه تعمل بسرعة أقل من سرعة وحدة المعالجة المركزية CPU..

نظرة عامة

وعلى صعيد آخر، هناك الكثير من الموارد المستعملة من قبل الحاسوب يمكن قياسها، أكثر اثنتين شائعتين هما السرعة واستخدام الذاكرة، عدا عن موارد أخرى يمكن أخذها بعين الاعتبار مثل سرعة النّقل ومدى استخدام الخوارزمية للذاكرة المؤقتة، واستهلاك الطاقة، ووقت الاستجابة.

علاوةً على ذلك، تعتبر الخوارزمية ذات كفاءة إذا كان استخدامها للموارد أقل من "المستوى المقبول"، ويمكن القول أن المستوى المقبول يعني أن الخوارزمية سوف تستهلك كمّا معقولاً من الموارد. منذ 1950، شهدت الحواسيب تطورًا كبيرًا بالنسبة لكل من الطاقة الحاسوبية المتاحة وكمية الذاكرة المتاحة، لذلك فإن مستويات القبول الحالية لا يمكن مقارنتها مع المستويات المقبولة قبل 10 سنوات مثلاً.

كذلك، الكثير من هذه المعايير يعتمد على حجم المدخلات للخوارزمية -كمية البيانات التي سيتم معالجتها-، وأحيانا تعتمد على طريقة ترتيب البيانات حيث أن بعض خوارزميات الترتيب يكون أداؤها سيّئاً عندما تكون البيانات مرتّبة مسبقاً، أو التي تكون مرتبة بطريقة عكسية.

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

مقياس استخدام الموارد

من جانب آخر، 2. المساحة: كمية الذاكرة (تحديداً الذاكرة العشوائية) التي تحتاجها الخوارزمية. والمساحة تُقسم إلى قسمين: حجم المساحة التي تحتاجها الشيفرة المصدرية للخوارزمية وحجم البيانات التي تعالجها الشيفرة.

  • يُعّبر عادةً عن المقياس من خلال اقتران مرتبط بحجم البيانات n
  • أكثر مِقياسّين يُعتمد عليهما هما:
  • 1. الزمن: مقدار الزمن الذي تستغرقه الخوارزمية لتنهي عملها.

الزمن

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.