Как рассчитать биномиальный коэффициент временной и пространственной сложности? (итеративный и рекурсивный)
Это итерационная версия, но она вызывает рекурсивную функцию. Повлияет ли это на сложность времени и пространства?
int factorial(int n) {
if (n == 1) {
return 1;
}
else {
return n * factorial(n - 1);
}
}
int binomial_coefficient_iterative(unsigned int n, unsigned int k) {
if (k == 0 || k == n) {
return 1;
}
else {
return (factorial(n) / ( factorial(k) * factorial(n - k) ) );
}
}
Это рекурсивная версия, рассчитанная по формуле C (n, k) = C (n-1, k) + C (n-1, k-1).
int binomial_coefficient_recursive(unsigned int n, unsigned int k){
if (k == 0 || k == n) {
return 1;
}
else {
return binomial_coefficient_recursive(n - 1, k) + binomial_coefficient_recursive(n - 1, k - 1);
}
}
И последнее, но не менее важное: можете ли вы рассчитать биномиальный коэффициент C (n, k), используя C (n, k-1)?
Решение
Оба решения зависят от рекурсии. В 1-й версии вы можете заменить рекурсивный вызов факториала простой итерацией.
Однако существует проблема пересчета перекрывающихся подзадач во 2-м решении.
C(n, k) = C(n-1, k) + C(n-1, k-1)
Вы должны использовать мемоизацию для кэширования значений C (n, k) всякий раз, когда оно вычисляется, сохраняйте значение, и когда функция вызывает с теми же параметрами вместо пересчета, ищите и возвращайте значение.
В первой задаче вы делаете несколько вызовов факториальной функции, которых можно избежать. Стратегия состоит в том, чтобы вычислить постепенное изменение. Например, когда вы вычисляете factorial(k) вы можете получить
factorial(n) = factorial(k) * K+1 * K+2 ...n
Это уменьшает количество умножения, которое вы делаете.
Возвращаясь к пространственно-временному усложнению проблемы.
1-е: временная сложность здесь O (n), так как для трех факторных вызовов вы выполняете умножение n, k и n-k
2-й: это будет
T(n,k) = T(n-1,k) + T(n-1,k-1) + O(1)
where T(n,n) = T(n,0) = O(1)
Решая это разностное уравнение, вы получите T (n) = O (2 ^ n), (тот же аргумент, который используется для определения сложности рядов Фибоначчи)
Таким образом, более поздний подход является экспоненциальным, который можно свести к минимуму с помощью запоминания.
Другие решения
Других решений пока нет …