查找函数

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)