(Для лучшего восприятия прочтите исходный пост здесь.)
Число Фибоначчи определяется как:
F(n) = F(n-1) + F(n-2), где F(0)=0,F(1)=1 .
Когда мы узнали, что такое рекурсия, ее можно напрямую записать в следующий наиболее распространенный код:
////////////////////////////////////////////////////////////////////
// Recursive: O(2^n)
uint64_t fibonacci(unsigned int n)
{
return (n <= 1) ? n : fibonacci(n-1) + fibonacci(n-2);
}Однако, если вы попытаетесь вычислить F(100), вам придется очень долго ждать результата, поскольку в нем так много перекрывающихся процессов. Например, если мы вычислим F(4), то будут дублированные вычисления (перекрывающиеся подструктуры) для F(2):
4
/ \
/ \
/ \
3 2
/ \ / \
2 1 1 0
/ \
1 0
Чем больше n, тем больше у нас пересекающихся процессов. В результате временная сложность составляет O(2^n).
ЗАПОМИНАНИЕ
Чтобы избежать этого, мы можем использовать кеш для сохранения всех результатов и проверки перед любым вычислением, поэтому все F(k), которые нам нужны, для k ∈ [0, n], будет вычислено только один раз. Следовательно, временная сложность может быть сокращена до O(n) с O(2^n).
////////////////////////////////////////////////////////////////////
// Recursive with memoization: O(n)
// F(k) = mem[k], F(0) = 0, F(1) = 1.
std::vector<uint64_t> mem = { 0, 1 };
uint64_t fibonacci(unsigned int n)
{
if (n + 1 > mem.size()) { // if n is not calculated yet
mem.push_back(fibonacci(n-1) + fibonacci(n-2));
}
return mem[n];
} ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
Приведенная выше реализация требует дополнительного места для сохранения результатов и затрат времени на выделение памяти. Если мы итеративно вычислим F(n) от F(0), F(1) до F(2), F(3), …,вF(n-1), F(n)или F(n), F(n+1), то мы можем использовать только две или три переменные, чтобы получить F(n):
////////////////////////////////////////////////////////////////////
// Dynamic programming: O(n)
uint64_t fibonacci(unsigned int n)
{
uint64_t a = 0, b = 1; // a = F(k), b = F(k+1), k = 0 now.
for (unsigned int k = 1 ; k <= n ; ++k) { // loop k from 1 to n.
std::swap(a, b); // a = F(k+1), b = F(k)
b += a; // b = F(k) + F(k+1) = F(k+2)
}
return a;
}or
////////////////////////////////////////////////////////////////////
// Dynamic programming: O(n)
uint64_t fibonacci(unsigned int n)
{
uint64_t a = 0, b = 1, sum = 0; // a = F(0), b = F(1)
for (unsigned int i = 1 ; i < n ; ++i) { // run if n >= 2
sum = a + b; // sum = F(i+1)
a = b; // a = F(i)
b = sum; // b = F(i+1)
}
// Now, i = n, sum = F(n), a = F(n-1), b = F(n)
return (n < 2) ? n : sum;
}Кроме того, они работают в режиме O(n) с меньшим потреблением памяти, чем метод memoization. Кроме того, они позволяют избежать накладных расходов памяти для записей активации в сегменте/пространстве стека для рекурсий. (Рекурсия будет вызывать себя несколько раз, поэтому она будет помещать несколько записей активации для одной и той же функции с разными аргументами в сегмент/пространство стека загрузки процесса. программа.)
ЗАКРЫТАЯ ФОРМА
На самом деле число Фибоначчи можно рассчитать по следующей формуле:
(Пожалуйста, прочитайте этот пост, чтобы узнать, как он получен.)
////////////////////////////////////////////////////////////////////
// closed-form: O(log(n))
uint64_t fibonacci(unsigned int n)
{
// double sqrt5 = sqrt((double)5);
double sqrt5 = 2.2360679775;
return (pow((1 + sqrt5) / 2, n) - pow((1 - sqrt5) / 2, n)) / sqrt5;
}Его временная сложность зависит от того, как рассчитывается мощность n. Это можно сделать за O(log n) времени (мы объясним это ниже). Однако операции с плавающей запятой ограничивают вычисляемое число n и могут снижать производительность.
МАТРИЧНАЯ АЛГЕБРА
Числа Фибоначчи можно записать в следующую матрицу:
, поэтому его можно легко расширить по тому же правилу:
(Пожалуйста, прочитайте этот пост для дальнейшего обсуждения.)
То есть матрица Фибоначчи превращается в совершенную степень. Применение возведение в степень возведением в квадрат:
, мы могли бы реализовать приведенную выше идею, чтобы:
////////////////////////////////////////////////////////////////////
// Power by matrix exponentiation: O(log(n))
// Matrix A:
// <--- cols: n --->
// +- -+
// | A11, A12, ... A1n | ^
// | A21, A22, ... A2n | |
// | ... | rows: m
// | ... | |
// | Am1, Am2, ... Amn | v
// +- -+
class Matrix
{
public:
Matrix(unsigned int r, unsigned int c,
std::vector<std::vector<uint64_t>> d)
: rows(r)
, cols(c)
, data(d)
{
}
Matrix(unsigned int r, unsigned int c)
: rows(r)
, cols(c)
{
assert(rows && cols);
data.resize(rows);
for (unsigned int i = 0 ; i < rows ; ++i) {
data[i].resize(cols);
}
}
~Matrix()
{
}
uint64_t Read(unsigned int r, unsigned int c)
{
return data[r][c];
}
Matrix operator*(const Matrix& other)
{
assert(cols == other.rows); // Check if they can be multiplied.
Matrix z(rows, other.cols);
for (unsigned int i = 0 ; i < rows ; ++i) {
for (unsigned int j = 0 ; j < other.cols; ++j) {
for (unsigned int k = 0 ; k < cols; ++k) {
z.data[i][j] += data[i][k] * other.data[k][j];
}
}
}
return z;
}
// Calculate the power by fast doubling:
// k ^ n = (k^2) ^ (n/2) , if n is even
// or k * (k^2) ^ ((k-1)/2) , if n is odd
Matrix pow(unsigned int n)
{
Matrix k(*this); // Copy constructor.
Matrix r = Identity(rows);
while (n) {
if (/*n % 2*/n & 1) {
r = r * k;
}
k = k * k;
/*n /= 2*/n >>= 1;
}
return r;
}
private:
Matrix Identity(unsigned int size)
{
Matrix z(size, size);
for (unsigned int i = 0 ; i < size ; ++i) {
z.data[i][i] = 1;
}
return z;
}
unsigned int rows;
unsigned int cols;
std::vector<std::vector<uint64_t>> data;
};
// The Fibonacci matrix can be written into the following equation:
// +- -+ +- -+^n
// | F(n+1) F(n) | | 1 1 |
// | | = | |
// | F(n) F(n-1) | | 1 0 |
// +- -+ +- -+
uint64_t fibonacci(unsigned int n)
{
Matrix F { 2, 2, {
{ 1, 1 },
{ 1, 0 }
} };
// Using F.data[0][1] since n might be 0.
// (we need to power by n - 1 if we return F.data[0][0].)
F = F.pow(n);
return F.Read(0, 1);
}Его временная сложность составляет O(log n) при делении пополам и пополам. Без операций с плавающей запятой n может быть больше, чем при использовании закрытой формы.
Чтобы сделать это быстрее, вы можете использовать собственный массив вместо std::vector, но вам нужно самостоятельно управлять использованием памяти. Пожалуйста, прочитайте этот пост, чтобы узнать, как это сделать.
БЫСТРОЕ УДВОЕНИЕ
Следующие уравнения:
можно получить, применив 2n к приведенной выше матрице Фибоначчи:
Следовательно, мы могли бы вычислить F(n) следующим образом:
Как следствие, F(n) можно вычислить с помощью следующей программы: (Пожалуйста, прочитайте этот пост, чтобы узнать, как получен код.)
uint64_t fibonacci(unsigned int n)
{
// The position of the highest bit of n.
// So we need to loop `h` times to get the answer.
// Example: n = (Dec)50 = (Bin)00110010, then h = 6.
// ^ 6th bit from right side
unsigned int h = 0;
for (unsigned int i = n ; i ; ++h, i >>= 1);
uint64_t a = 0; // F(0) = 0
uint64_t b = 1; // F(1) = 1
// There is only one `1` in the bits of `mask`.
// The `1`'s position is same as
// the highest bit of n(mask = 2^(h-1) at first),
// and it will be shifted right iteratively to do
// `AND` operation with `n` to check `n / 2^j` is odd
// or even.
for (unsigned int mask = 1 << (h - 1) ; mask ; mask >>= 1) {
// Let j = h-i (looping from i = 1 to i = h),
// n_j = floor(n / 2^j) = n >> j (n_j = n when j = 0),
// k = floor(n_j / 2), then a = F(k), b = F(k+1) now.
uint64_t c = a * (2 * b - a); // F(2k)=F(k) * [2*F(k+1)–F(k)]
uint64_t d = a * a + b * b; // F(2k+1) = F(k)^2 + F(k+1)^2
if (mask & n) { // n_j is odd: k = (n_j-1)/2 => n_j = 2k + 1
a = d; // F(n_j) = F(2k + 1)
b = c + d; // F(n_j + 1) = F(2k + 2) = F(2k) + F(2k + 1)
} else { // n_j is even: k = n_j/2 => n_j = 2k
a = c; // F(n_j) = F(2k)
b = d; // F(n_j + 1) = F(2k + 1)
}
}
return a;
}Его временная сложность также составляет O(log n) при уменьшении вдвое. В отличие от подхода матричной алгебры, нет необходимости использовать какой-либо массив или вектор для содержания дублированного F(k) в матрице, поэтому это будет быстрее.
ПРЕДСТАВЛЕНИЕ
Приведенные выше результаты представляют собой время в миллисекундах для вычисления F(n). Получение результатов при использовании рекурсивного подхода займет слишком много времени, поэтому мы его пропускаем. Подход с закрытой формой также игнорируется, так как операции с плавающей запятой работают только при n≤97 в реализации выше.
ВЫВОД
Хотя производительность зависит от платформы, она по-прежнему указывает на то, что:
- Подход быстрого удвоения всегда является самым быстрым способом, и его производительность намного выше, чем у других.
- Подход динамического программирования работает быстрее, чем метод матричной алгебры, когда nn мало (n≤13000 здесь), но медленнее, когда n большой.
- Поэтому, если вы почти уверены, что у вас небольшое n, и узкое место вашего алгоритма не зависит от расчета Фибоначчи, тогда динамическое программирование приемлем и его проще реализовать.
Этот пост — конец моего пути к расчету Фибоначчи. Надеюсь тебе понравилось. Весь приведенный выше код загружается в суть здесь. Пожалуйста, клонируйте их, чтобы поиграть с ними.
Я скоро начну новое путешествие по другим интересным темам. Быть в курсе!
