Komplexität des Min-Max-Algorithmus

Question

Ich habe den folgenden Code. Welche Rekursionsbeziehung sollte für sie gelten und was wird ihre Komplexität sein? Es wird wirklich nett sein, wenn Sie mir helfen können, seine Komplexität zu finden, indem Sie die Rekursionsbeziehung mit der Substitutionsmethode lösen.

Knotenvariable mehrere Rückgabe zum Speichern von Werten

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

rekursive Funktion, die die minimale und maximale Zahl von einem gegebenen Array

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

Jeder Aufruf findet

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; 

} 

Hauptfunktion partition führt eine konstante Menge an Arbeit, plus 2 zusätzliche re kursive Aufrufe, jeweils mit halb des Eingangsindexbereichs. Wir können somit eine Rekursion für die Zeitkomplexität Funktion konstruieren:

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

Dies erweitert zu einer geometrischen Reihe C * (1 + 2 + 4 + ...), der die Eingangsgröße Hälften für log n Bedingungen (weil auf jeder Ebene der Rekursion fortsetzt, so sie verringert sich geometrisch auf die Stoppbedingung n = 2). Aus Standardformeln entspricht dies O(n).

---

EDIT: Gleichungen auf der vorhergehenden Erklärung zu verbessern: