具有两个循环和两个递归调用的算法的时间复杂度 [英] Time complexity of an algorithm with two loops and two recursive calls

问题描述

这是一种通过两个递归调用对数组进行排序的算法。我试图粗略计算其时间复杂度但不确定。我知道两个for循环将花费n + n次，但是递归调用的处理方式以及如何我可以计算出来吗？
任何人都可以用简单的数学方法来帮助计算。

Here is an algorithm of sorting an array with two recursive calls.I have tried to calculate its time complexity roughly but not sure.I know that two for loops will take n+n times but what to do with recursive calls and how can i calculate them? Any one can help in calculating in simple mathematical way.

MySort (a[1..n] , n) {

         If (n <= 2) {
            If (first element > second) && (n = 2) then do
               { Interchange a[1] & a[2]; }
         End if
         }
         Else
         { Assign value to min and max by very first element of array.
         for (i : = 1 to n) do 
            { If (a[i] > max) then
              max = a[i]; 
         Else if (a[i] < min) then
                  min = a[i]; //Get max and min element from the array. }
         End for
         Calculate MID value of the MAXIMUM & MINIMUM element found. 
         For i : = 1 to n do 
         {
            If(a[i] < mid) then { Increment Count1 by 1; and P[Count1]=a[i] }
            Else if (a[i] > mid) then { Increment Count2 by 1; and Q[Count2]=a[i] } 
    //Divide the major array to sub-arrays; 
    //Count1 and Count2 are counters to make check on the size of sub-arrays generated. 
             }
        End for
        MySort (P, Count1);
           MSort (Q, Count2); }
        End if}

推荐答案

有两个循环后跟两个递归调用。理想情况下，每个调用将输入的大小减半，从而得到n / 2个值。这给出了递归关系：

There are two loops followed by two recursive calls. Ideally, each call would halve the size of the input, resulting in n/2 values. This gives a recurrence relation:

T(n) = n + n + T(n/2) + T(n/2)
T(n) = 2n + 2T(n/2)

此匹配项主定理页面上给出的表格的最后一行：

This matches the last row of the table given on the Master theorem page:

T(n) = O(nlogn)

如果每个呼叫的输入输入不是平均分配的，那么它将花费n ^ 2的时间，因为每次呼叫的大小只能减少1：

If the input input is not evenly divided each call, then it instead takes n^2 time, as the size could possibly only be reduced by 1 each call:

T(n) = 2n + T(n-1) + T(1)
T(n) = nT(1) + 2n + 2(n-1) + 2(n-2) + ...
T(n) = O(n^2)

这篇关于具有两个循环和两个递归调用的算法的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！