查找函數

Question

我必須找到以下函數的遞歸方程的遞歸方程：

static int f(int[] a, int inf, int sup) { 
    if(sup == inf) 
     return a[inf]; 
    if(sup == inf+1) 
     return a[inf] + a[sup]; 
    else { 
     int thrd = (sup - inf + 1)/3; 
     int i = inf + thrd; 
     int j = i + thrd; 
     int sum = 0; 
     for(int k = i; k < j; k++) 
      sum += a[k]; 
     return f(a, inf, i-1) + f(a, j, sup) + sum; 
    } 
} 

基礎案例是T（1）= 1（從if(sup == inf)到sum += a[k];）。 而是遞歸的情況是什麼？我要說T（N）= 2T（N/3）+ 1，但我不知道..

感謝

Answer 1

下面是你的遞歸的情況下各行的成本

static int f(int[] a, int inf, int sup) { 
    if(sup == inf) 
    return a[inf]; 
    if(sup == inf+1) 
    return a[inf] + a[sup]; 
    else { 
    int thrd = (sup - inf + 1)/3;     //O(1) 
    int i = inf + thrd;       //O(1) 
    int j = i + thrd;        //O(1) 
    int sum = 0;         //O(1) 
    for(int k = i; k < j; k++) sum += a[k];  //O(n/3) 
    return f(a, inf, i-1) + f(a, j, sup) + sum; //2 * T(n/3) 
    } 
} 

O（n/3）來自您的for循環迭代超過您輸入大小的三分之一，而2 * T（n/3）項來自事實上我們正在遞歸三分之一的輸入大小的兩倍。這給我們

T(n) = O(1) + O(1) + O(1) + O(1) + O(n/3) + 2 * T(n/3) 

由於O（1）+ O（1）是靜止O（1），前4 O（1）的崩潰成一個單一的術語，併爲O（n/3）是與O（n）相同，我們剩下了

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