ما هي الكيفية لحساب درجة التعقيد لخوارزمية معينة؟

مقدمة

حساب تعقيد خوارزمية معينة له بعدين اساسيين هما: الوقت Time والمساحة Space.

لنفرض ان لدينا خورزميتين اثنتين A و B يؤديان نفس الغرض لكن A يستهلك ١٠ كيلوبايت مساحة و ٤ ثواني بينما B يستهلك ١٥ كيلوبايت مساحة و 6 ثواني .. لاشك أن خوارزمية A افضل او بالاصح أكفأ more efficient من B

الوقت يتضمن المساحة - بمعنى ان حجز مساحة ١٠٠ متغير تاخذ وقت اكثر من حجز مساحة ١٠ متغيرات.. فلذلك تعقيد الخوارزمية عادة ينصب على الوقت.

---

حتى نتمكن من حساب تعقيد الخوارزمية -الوقت اللازم لتنفيذ الخوارزمية- لابد ناخذ معيار يتوفر فيه الاتي:

١. ليس له علاقة بالمؤثرات الخارجية للخوارزمية ( لغة البرمجة المستعملة، سرعة الجهاز/الكومبايلر ..الخ )

٢. يكون له علاقة بطبيعة عمل الخوارزمية.

المقصد في الشرط الاول ان تعقيد الخوارزمية يبقى نفس الشئ مهما اختلفت الاجهزة والادوات المتاحة للمطور.

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

مثلاً طبيعة خوارزمية ترتيب اعداد تختلف عن خوارزمية ايجاد cycle في قراف. في الأولى الخوارزمية تقوم بعمل مقارنة بين الاعداد وفي الثانية تقوم بالمشي traverse على القراف.

---

لنفرض ان لديك خوارزمية لترتيب الاعداد - من الاصغر الى الاكبر- في مصفوفة اعداد array من حجم n ..

العملية الأساسية لمثل هذه الخوارزمية هي المقارنة comparison بين عددين من المصفوفة للنظر ايهما اصغر ..

بالتاكيد ترتيب مصفوفة من ١٠ عناصر اسهل من ترتيب مصفوفة من ١٠٠ عنصر .. لذلك حجم المدخلات للخوارزمية عادة يكون هو مايقاس به تعقيدها (في حالتنا حجم المصفوفة n ) . ولذلك لحساب تعقيد الخوارزمية عادة لانهتم بالثوابت والاعداد الاخرى .. نهتم بوقت الخوارزمية مقارنة مع حجم المدخلات. مثلاً لو ان لدينا خوارزمية معينة بحجم مدخلات n لكن عدد الخطوات الاساسية التي تعملها هي 5*n فاننا نقول ان تعقيد الخوارزمية هو n .. هذا مايسمى تعقيد Asymptotic بمعنى اننا نحسب التعقيد عندما يكون n كبير ولانهتم بالعوامل الجانبية.

---

لناخذ خوارزمية Bubble sort لترتيب اعداد المصفوفة مثلاً ..

for i=1 to n
{
for j=i+1 to n 
if array[j]<array[i] then swap 
}

هذا منظر مريع لخوارزمية.. لكن كم عدد المقارنات التي تتم هنا ؟

في اسوء الاحوال فان اللوب الاول سيتم تنفيذه n مره واللوب الثاني سيتم تنفيذه n-1+n-2+....+1

لذلك تعقيد هذه الخوارزمية هو n+(n-1+n-2+...+1)=n(n-1)/2=n^2-n/2=n^2

ويرمز لها بالرمز O(n^2) لاحظ اننا تغافلنا عن الاعداد الاخرى .. علمياً في هذه الحالة نقول ان تعقيد الخوارزمية quadratic بمعنى تربيعي n^2 ..