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

ما هو تعقيد الوقت؟

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

تحليل المقاييس المتكررة

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

الطرائق المشتركة للحساب

وتستخدم طريقتان أوليتان لحل العلاقات المتكررة:

  • Substitution Method:] guess the solution and verify it through induction.
  • Recursion Tree Method:] Visualize the recurrence as a tree to sum the costs at each level.

فعلى سبيل المثال، تصف التكرار T(n) = 2T(n/2) + n) خوارزمية تقسيم وثغرة.