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

تعقيد الوقت

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

1. الوقت الثابت – O(1):

   • لا يتغير وقت تنفيذ الخوارزمية مع حجم الإدخال.
   • مثال: الوصول إلى عنصر في مصفوفة حسب الفهرس، كما في arr[5].

2. الوقت اللوغاريتمي – O(log n):

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

3. الوقت الخطي – O(n):

   • يزداد وقت تنفيذ الخوارزمية خطيًا مع حجم الإدخال.
   • مثال: اجتياز مصفوفة من العناصر n مرة واحدة.

4. الوقت الخطي – O(n log n):

   • شائع في خوارزميات الفرز الفعالة حيث يتم التعامل مع كل عنصر لوغاريتميًا، عادةً بسبب التقسيم العودي والدمج الخطي أو المعالجة.
   • مثال: دمج الفرز، الفرز السريع.

5. الزمن التربيعي – O(n²):

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

6. الوقت المكعب – O(n³):

   • يزداد وقت التنفيذ مع مكعب حجم الإدخال. نادر ولكن يمكن أن يحدث في الخوارزميات ذات ثلاث حلقات متداخلة.
   • مثال: حل عمليات مصفوفة معينة باستخدام خوارزميات القوة الغاشمة.

7. الزمن الأسي – O(2^n):

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

8. الوقت المضروب – O(n!):

   • يزداد وقت التنفيذ بشكل مضاعف مع حجم الإدخال. غالبًا من الخوارزميات التي تتضمن إنشاء جميع التباديل أو المجموعات الممكنة.
   • مثال: حل مشكلة البائع المتجول بالقوة الغاشمة.

تعقيد الفضاء

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

1. مسافة ثابتة – O(1):

   • تستخدم الخوارزمية مقدارًا ثابتًا من الذاكرة بغض النظر عن حجم الإدخال.
   • مثال: تخزين بعض المتغيرات، مثل الأعداد الصحيحة أو العدادات.

2. الفضاء اللوغاريتمي – O(log n):

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

3. الفضاء الخطي – O(n):

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

4. الفضاء التربيعي – O(n²):

   • يزداد استخدام الذاكرة مع مربع حجم الإدخال، كما هو الحال عند تخزين مصفوفة ثنائية الأبعاد بحجم n x n.
   • مثال: تخزين مصفوفة مجاورة لرسم بياني بعدد n من العقد.

5. الفضاء الأسي – O(2^n):

   • ينمو استخدام الذاكرة بشكل كبير مع حجم الإدخال، غالبًا في الحلول المتكررة التي تخزن البيانات لكل مجموعة فرعية محتملة من الإدخال.
   • مثال: الحفظ في الخوارزميات العودية مع العديد من المشاكل الفرعية المتداخلة.

أمثلة عملية

• الوقت الخطي (O(n)) والمسافة الخطية (O(n)):

  • دالة تتكرر خلال مصفوفة وتخزن كل عنصر في مصفوفة جديدة.

• الزمن التربيعي (O(n²)) والفضاء الثابت (O(1)):

  • دالة تحتوي على حلقتين متداخلتين على مصفوفة ولكنها لا تتطلب مساحة تخزين إضافية تتجاوز بعض المتغيرات.

تحليل التعقيد

عند تحليل التعليمات البرمجية لتعقيد الزمان والمكان:

1. تحديد الحلقات: الحلقات المتداخلة عادة ما تزيد من التعقيد (على سبيل المثال، حلقة واحدة تعطي ( O(n) ); حلقتان متداخلتان تعطي ( O(n^2) )).
2. ابحث عن العودية: يمكن أن تؤدي الاستدعاءات العودية إلى تعقيد كبير في الزمان والمكان، اعتمادًا على عامل التفرع وعمق العودية.
3. ضع في اعتبارك هياكل البيانات: يمكن أن يؤثر استخدام هياكل البيانات الإضافية مثل المصفوفات أو القوائم أو خرائط التجزئة على تعقيد المساحة.

نصائح عامة

• تعقيد الوقت يتعلق بإحصاء العمليات كدالة لحجم الإدخال.
• تعقيد المساحة يتعلق بحساب مقدار الذاكرة الإضافية المطلوبة.

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