كيفية حساب الcomplexity time لخوارزمية

لا يوجد طريقة ثابتة لحساب التعقيد الوقتي, حيث أنه يتم إثباته أكثر مما يتم حسابه

ولكن بوجهٍ عام التعقيد الوقتي هو كمية التعليمات التي يتم تنفيذها في الخوارزمية بالنسبة إلى عدد العناصر

يوجد بعض النقاط التي يمكننا إتباعها عند محاولتنا لتحليل الخوارزمية بغرض إيجاد التعقيد الوقتي 

1. يمكننا تحويل الحلقات التكرارية من رقم ثابت إلى n إلى مجموع حسابي summation, على سبيل المثال يمكننا تحويل 

   for(int i=a;i<n;i++)
       doSomeCalculation();

   إلى summation من a حيث a عدد ثابت إلى n ,والتي تساوي (n-a)*c حيث c أيضًا عدد ثابت وبالتالي يمكننا إختزال الثوابت ليصبح التعقيد الوقتي على شاكلة O(n) 

2. إن كانت الحلفة التكرارية تزيد بمقدار ضرب أو قسمة وليس جمع أو طرح على سبيل المثال 

   for(int i = a; i<n; i*=2)
     doSomeThing();
                     

   يكون هنا الsummation من a إلى log2n وبالتالي يصبح التعقيد الوقتي O(n) 

3. إن كان لدينا أكثر من حلقة تكرارية نقوم بفك الحلقة الداخلية ثم الأكبر ثم الأكبر , على سبيل المثال 

   for(int i=0;i<n;i++)
     for(int j=0;j<n;j++)
     	doSomeThing();

   نقوم بفك الحلقة الداخلية التي تعطينا n والخارجية التي تعطينا n*n = n^2 ويصبح بالتالي التعقيد O(n^2) 

4. في حالة ظهور recursion نقوم بتحويله إلى حلقة تكرارية وتطبيق السابق عليه

ويوجد أيضاً خوارزميات بتعقيد زمني كبير مثل التعقيد الأسي 

2^n

وهذه الخوارزمية لها تعقيد كبير جداً و تأخذ وقتاً كبيراً لذلك من المهم إيجاد طرق تفكير و خوارزميات لتحل المشاكل البرمجية بكفائة أكبر.

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

int fib(int n)
{
    if (n <= 1)
        return n;
    return fib(n-1) + fib(n-2);
}

لذلك لكل استدعاء دالة سيتم عمل استدعائين، فتكون علاقة عودية ذات تعقيد أسي

Fn = Fn-1 + Fn-2


                          fib(5)   
                     /                \
               fib(4)                fib(3)   
             /        \              /       \ 
         fib(3)      fib(2)         fib(2)   fib(1)
        /    \       /    \        /      \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /     \
fib(1) fib(0)

لاحظ تطبيق نفس فكرة الخوارزمية، لتصبح بتعقيد خطي (N)O بالاستفادة من المجموع التراكمي في مصفوفة حيث تمكننا من حساب حدود كبيرة (أكثر من التعاودية لحدود الوقت و الذاكرة)

int fib[24];

fib[0] = 0;
fib[1] = 1;

for(int i = 2; i < 24; i++)
  fib[i] = fib[i-1] + fib[i-2];

يمكنك قراءة المقالة التالية:

ودرس تحليل الخوارزميات من موسوعة حسوب