Определение рекуррентного отношения для данного алгоритма

void function(int A[], int i, int j){
    if (j == i+1) 
        if (A[i] > A[j])
            swap(A,i,j)
        else {
            int k = (j-i+1)/3;
            function(A,i,j-k); 
            function(A,i+k,j);
            function(A,i,j-k); 
        }
}

Этот фрагмент кода взят из прошлого промежуточного экзамена в моем классе анализа алгоритмов. Студентов попросили вывести рекуррентное соотношение, описывающее поведение этой функции. Я видел в Интернете несколько примеров того, как выполняется этот процесс, но я просто не могу понять, как применить его к этой конкретной функции, индексы i и j меня действительно сбивают с толку.

Любые идеи?


recurrence algorithm
person user43389    schedule 11.12.2015    source источник
comment
Попробуйте создать образец массива (10 элементов или около того) и вычислить, какими становятся фактические значения индексов.   -  person David    schedule 12.12.2015

Ответы (1)


arrow_upward
1
arrow_downward

Каждый из [i,j-k],[i+k,j],[i,j-k] является 2/3 из [i,j]. Итак, вы делите свою проблему на 3 части, когда каждая часть составляет две трети исходного размера. Следовательно, ваше рекуррентное отношение T(n) = 3*T(n*2/3). Вы можете решить эту проблему, используя основную теорему.

person Saeid    schedule 11.12.2015