min-max算法的複雜性

我有以下代碼。什麼樣的復發關係應該適用於它，以及複雜性如何。如果你可以通過使用替代方法解決遞歸關係來幫助我找到它的複雜性，那將是非常好的。min-max算法的複雜性

節點變量來存儲多個返回值

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

遞歸函數，從一個給定的陣列

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; 
}

來源

2017-08-13 Navdeep

每次調用找到最小和最大數字partition執行恆定的工作量，再加上2個額外的re草書呼叫，每個都有一半的的輸入索引範圍。因此，我們可以構建爲時間複雜功能的遞推關係：

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

此膨脹到幾何級數C * (1 + 2 + 4 + ...)，其持續log n術語（因爲在遞歸半部輸入大小的每個電平，從而它在幾何上減小到停止條件n = 2）。從標準公式，這相當於O(n)。

編輯：方程來提高先前的解釋：

$enter image description here$

來源

2017-08-13 09:57:59 meowgoesthedog

能否請您拓展上面說的公式，並證明它是O（N）？ – Navdeep

@Navdeep已更新 – meowgoesthedog

我認爲每次都會添加C ......請檢查一下......對於第K步，它應該是Ck。 – Navdeep

min-max算法的複雜性

回答

相關問題