Обречен на решение рекуррентного уравнения
Вот уравнение, с которым я работаю (это из предыдущего экзаменационного вопроса, который я ошибся):
void foo(float[] array, int start, int end){
if((end-start) <= 1) return;
int x = (end-start) / 5;
int y = 2*x;
int z = 4*x;
foo(array,start,start+y);
for(index = y; index <z; index++){
array[index]++;
}
foo(array,start+z,end);
}
Как мне придумать уравнение повторения для этого?
Я не уверен в нотации, которую я должен использовать, так как функция #recurferences зависит от значения end-start …
T (1) = 1
T (N) = ____ + ____ + _____
Решение
for notation simplicity, lets call N = end-start
then:
foo(array,start,start+y); // T(2/5 * N)
for(index = y; index <z; index++) // 2/5 * N
foo(array,start+z,end); // T(N/5)
T(N) = T(2/5 * N) + 2/5 * N + T(N/5)
это достаточно близко?
Другие решения
Других решений пока нет …