math - O(N) 最坏情况的 MaxMin 分而治之算法

Question

该算法的 T(N) 为 O(N^2)，最坏情况。当它是二的幂时，它是 O(N)。但是我需要找到一种方法让它在最坏的情况下成为 O(N)。有什么想法吗？

max_min(A, i, j, max, min)
{ 
  if(i==j)  -----------> 0 comparisons  
 {
     max=min=A[i];  
   return (max,min);  
  } 
   if(i=j-1)  
  { 
      if(A[i]>A[j])   -------------> 1 comparisons  
     { 
        max=A[i];  
        min=A[j]; 
      }  
     else   
    { 
        max=A[j];   
        min=A[i];
    }
  }
  else 
 {  
   mid=(i+j)/2; ----> O(1)   
  (max1,min1)=max_min(A, i, mid, max, min);  --->T(n/2)  
   // if T(n) is complexity for n elements
  (max2,min2)=max_min(A, mid+1, j, max. min); ---->T(n/2)     
    if(max1>max2)  ---> 1 comparisons   
      max=max1;
    else  
      max=max2; 
    if(min1>min2)  ---> 2 comparisons  
      min=min2;   
    else  
     min=min1; 
  }  
  return(max,min);
} 

Answer 1

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

有解(通过代入上面确认)

T(n) = (3/2)n - 2

对于 n 的 2 次幂是精确的，其中递归在所有递归级别都是精确的，并且不需要正确说明下限和上限。

正如我们从主定理的证明中得知的那样，地板和天花板不会改变解的渐近行为，因此 T(n) 通常是线性时间。所以没有问题要回答。