Ускорение функции с динамическим программированием
У меня есть эта программа
//h is our N
static int g=0;
int fun(int h){
if(h<=0){
g++;
return g;
}
return g+fun(h-1)+fun(h-4);
}
Действительно ли возможно ускорить его использующий динамическое программирование?
Я выяснил, что эта функция работает в O (2^n)
Я, как предполагается, уменьшаю время выполнения динамическим программированием, но не понимаю понятия.
Просто прося пошаговое перемещение в правильном направлении.
1 ответ
Хотя я не могу дать ответа на ваш вопрос, меня заинтриговало совсем другое, а именно утверждение
return g+fun(h-1)+fun(n-4);
Очевидно, ваша функция имеет побочный эффект изменения глобальной статической переменной g . Я не уверен на 100%, действительно ли выражение оператора return вычисляется четко определенным образом или результат может быть неопределенным.
Было бы неплохо подумать о порядке, в котором выполняются эти вызовы функций, и о том, как это влияет на g и, следовательно, на результат функции.