min-maxアルゴリズムの複雑さ

Question

私は以下のコードを持っています。再発の関係はどのようなものであり、その複雑さは何か。置換方法を使って再帰関係を解くことで複雑さを見いだすことができれば本当にうれしいです。複数の戻りを格納する

ノード変数は、指定された配列

struct node partition(int a[], int first, int last) 
{ 
    int MAX, MIN; 
    int low = first; 
    int high = last; 
    struct node left, right; 

    /*If there is a single variable */ 
    if (low==high) 
    { 
     NODE.MAXX = a[low]; 
     NODE.MINN = a[low]; 
     return(NODE); 
    } 
    /*If there exists only 2 elements*/ 
    else if (high==low+1) 
    { 
     if (a[high]>a[low]) 
     { 
      NODE.MAXX = a[high]; 
      NODE.MINN = a[low]; 
     } 
     else 
     { 
      NODE.MAXX = a[low]; 
      NODE.MINN = a[high]; 
     } 
     return NODE; 
    } 
    /*If there exists more than 2 elements */ 
    int mid = (low + high)/2; 
    left=partition(a, low, mid); 
    right=partition(a, mid+1, high); 
    if (left.MAXX > right.MAXX) 
     NODE.MAXX = left.MAXX; 
    else 
     NODE.MAXX = right.MAXX; 
    if (left.MINN < right.MINN) 
     NODE.MINN = left.MINN; 
    else 
     NODE.MINN = right.MINN; 

    return NODE; 

} 

メイン関数

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    struct node N; 
    int a[] = { 70, 50, 111, 69, 4, 7, 80, 100 }; 
    N=partition(a, 0, 7); 
    cout << "Maximum = " << N.MAXX << endl; 
    cout << "Minimum = " << N.MINN << endl; 
} 

Answer 1

各コールへの最小値および最大値を見つけ

struct node 
{ 
    int MAXX; 
    int MINN; 
}NODE; 

再帰関数値partitionは一定量の作業と2回の追加作業を行いますそれぞれが半分の入力索引範囲を持つ桁詰めコールです。したがって、

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

これが原因再帰入力サイズの半分の各レベル（log n用語継続等比級数C * (1 + 2 + 4 + ...)、に展開：我々は、このように時間計算機能のため漸化式を構築することができます幾何学的に停止状態n = 2まで減少します）。標準式から、これはO(n)に相当します。

---

EDIT：方程式は、前の説明を改善します