Нахождение рекуррентных уравнений функции

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

Базового случай Т (1) = 1 (от if(sup == inf) до sum += a[k];). Вместо этого рекурсивный случай, что есть? Я бы сказал Т (п) = 2Т (п/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) 's коллапс в один срок, и О (п/3) то же, что и O (n), мы остаемся

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