Ряд Фибоначчи
У меня проблемы с анализом времени и сложности. Я выполнил серию Фибоначчи рекурсивным способом. Я думаю, что это O (n 2 ) . Вы можете узнать временной анализ? Если возможно, не могли бы вы его уточнить?
#include<iostream>
using namespace std;
void fibonacci(int n,int n1,int n2)
{
if(n==0)
{
cout<<endl<<n1;
return;
}
else if(n==1)
{
cout<<endl<<n2;
return;
}
fibonacci(n-1,n2,n1+n2);
return;
}
int main()
{
int n;
cout<<"Enter the number:"<<endl;
cin>>n;
fibonacci(n,0,1);
return 0;
}
Ответы
Я не уверен, что какой-либо из ответов действительно касается сложности. Я собираюсь сделать это, преобразовав ваш алгоритм в более простой без изменения временной сложности. Это не только доказывает временную сложность, но и дает вам версию алгоритма, которую было бы легче читать и рассуждать.
Начнем с вашего решения
void fibonacci(int n,int n1,int n2)
{
if(n==0)
{
cout<<endl<<n1;
return;
}
else if(n==1)
{
cout<<endl<<n2;
return;
}
fibonacci(n-1,n2,n1+n2);
return;
}
Эта else ifчасть на самом деле не нужна, поэтому давайте удалим ее, а также избавимся от лишних returnкоманд. [См. Комментарии для обсуждения того, почему этот шаг не так невинен, как кажется.]
void fibonacci(int n,int n1,int n2)
{
if(n==0) {
cout<<endl<<n1; }
else {
fibonacci(n-1,n2,n1+n2); }
}
Поменяйте местами if. Также я собираюсь вернуть один из них returnи снять распечатку с elseдетали.
void fibonacci(int n,int n1,int n2)
{
if(n!=0) {
fibonacci(n-1,n2,n1+n2);
return ; }
cout<<endl<<n1;
}
Примените оптимизацию хвостовой рекурсии, т. Е. Замените рекурсивный вызов и следующий за ним возврат переназначением параметров и переходом к началу подпрограммы. Этот шаг изменит сложность пространства *, но не временную сложность.
void fibonacci(int n,int n1,int n2)
{
start:
if(n!=0) {
int sum = n1+n2 ;
n1 = n2 ;
n2 = sum ;
n = n-1 ;
goto start ; }
out<<endl<<n1;
}
Используйте цикл вместо goto.
void fibonacci(int n,int n1,int n2)
{
while(n!=0) {
int sum = n1+n2 ;
n1 = n2 ;
n2 = sum ;
n = n-1 ; }
cout<<endl<<n1;
}
На самом деле вам не нужно, чтобы параметры были параметрами. Я бы, наверное, задокументировал подпрограмму, чтобы было понятно, что она делает. И я бы задокументировал цикл while с инвариантом, чтобы было более понятно, как он работает.
void fibonacci(int n)
// Precondition: n >= 0
// Postcondition: the value of fib(n) has been printed to standard out
// preceded by an end of line.
{
int n1 = 0 ;
int n2 = 1 ;
// Let n0 be the original value if n.
// invariant n1 == fib( n0-n ) and n1 == fib(n0-n+1)
while(n!=0) {
int sum = n1+n2 ;
n1 = n2 ;
n2 = sum ;
n = n-1 ; }
cout<<endl<<n1;
}
(И, конечно, поменять место, где он называется.)
На данный момент ясно (я думаю), что алгоритм O (n). Ни одно из преобразований не меняет временную сложность, поэтому временная сложность оригинала также O (n).
(*) То есть он изменит сложность пространства с O (n) на O (1), если ваш компилятор не выполняет оптимизацию хвостовой рекурсии. Если это так, сложность пространства с самого начала была O (1).
Около using namespace std
Вам следует избегать этого утверждения, так как это считается плохой практикой . По возможности лучше избегать этого. Вот простой пример, почему.
#include <iostream>
#inlcude <list>
using namespace std;
class list // uh-hoh, list is already defined, or is that std::list?
{
...
};
Другая проблема заключается в том, что если у вас есть это в любом из файлов заголовков в вашем проекте, вы будете вынуждены использовать это в любом файле, который вы включили в заголовок.
Почему использование пространства имен std считается плохой практикой
Мета-программирование шаблонов
Это перемещает расчет из времени выполнения во время компиляции . Компиляция вашей программы займет немного больше времени, но будет сложность O(1). Он использует шаблоны в C ++, чтобы заставить компилятор вычислить значение.
Это еще один вариант решения этой проблемы и самый быстрый способ, поскольку при этом расчет перемещается во время компиляции .
Однако недостатком является то, что вы не можете использовать значения, которые неизвестны во время компиляции. Например, вы можете найти значение, 5но не то, что введет пользователь, или, например, сгенерированное случайное число.
#include<iostream>
template <unsigned N>
struct Fibonacci
{
enum : uint64_t
{
value = Fibonacci<N-1>::value + Fibonacci<N-2>::value
};
};
template <>
struct Fibonacci<1>
{
enum
{
value = 1
};
};
template <>
struct Fibonacci<0>
{
enum
{
value = 0
};
};
int main()
{
std::cout << Fibonacci<20>::value;
}
Этот метод будет самым быстрым, но будет работать только в том случае, если ваши числа постоянны.
Мета-программирование шаблонов на C ++
Заменить рекурсию на итерацию
Хотя рекурсия делает ваш код немного чище, рекурсия почти всегда выполняется медленнее , потому что для каждого вызова требуется выделение нового кадра стека.
Из-за того, что пространство в стеке ограничено , существует ограничение на количество рекурсивных вызовов вы можете сделать, прежде чем C ++ даст вам 0xC00000FD. Это переполнение стека.
Еще несколько строк кода, и вы можете заменить рекурсию этим сценарием и сделать его намного быстрее без этой проблемы.
Это не означает, что вы не должны использовать рекурсию, некоторые алгоритмы нуждаются в рекурсии, но если вы можете заменить ее итерацией, то это того стоит.
Вот оно с итерацией.
uint64_t fibonacci(int n)
{
uint64_t n1 = 0,n2 = 1,n3 = 1;
if (n == 1 || n == 0) return 0;
else if(n == 2) return 1;
for (int i = 2;i < n;++i)
{
n3 = n1 + n2;
n1 = n2;
n2 = n3;
}
return n3;
}
'\n' над std::endl
'\n'и std::endlоба выполнят вашу задачу, но каждый раз std::endlвызывают std::flushи сбрасывают поток, поэтому он будет медленнее, чем просто печать'\n'
Сравнение std :: endl и '\ n'
Самый очевидный способ написать фибу:
int fib(int n)
{
if (n < 2) // 0 or 1
{
return 1;
}
return fib(n-1) + fib(n-2);
}
Вы можете видеть, как он взрывается, потому что для каждого вызова fib () вы получаете 2 последующих вызова, оба из которых получают 2 вызова, все получают 2 вызова и т. Д.
Level Calls Calls This Level Total Calls
Level n 1 1 1
Level n-1 1 1 2 3
Level n-2 1 1 1 1 4 7
Level n-3 1 1 1 1 1 1 1 1 8 15
Итак, сложность Фибоначчи равна Фибоначчи !!!!!
Точнее, завершенность - это O(2Fib(n)-1)
удаление константO(Fib(n))
Давайте напишем код, чтобы проверить это:
int fibComplexity(int n)
{
// has the same properties of fib.
// but returns the number of calls rather than the value.
if (n < 2)
{
return 1; // You called this function once.
}
return 1 // the call to this function.
+ fibComplexity(n-1) // Count of calls in this tree
+ fibComplexity(n-2) // Count of calls in this tree.
}
Если мы проиграем это:
int main()
{
for(int loop = 2; loop < 15; ++loop)
{
std::cout << loop << " " << fib(loop) << " " << fibComplexity(loop) << "\n";
}
}
Генерирует: (добавлено форматирование)
n F O
2 2 3
3 3 5
4 5 9
5 8 15
6 13 25
7 21 41
8 34 67
9 55 109
10 89 177
11 144 287
12 233 465
13 377 753
14 610 1219 O = 2f-1
Но каждый курс кодирования, который вы пройдете, затем попросит вас создать линейное решение.
То, что вы представляете выше, является рекурсивным (но линейным) решением. Большинство людей выбрало бы линейное решение на основе цикла (но нет никакой разницы). Сложность точно такая же.
То, что вы сделали, - это рекурсивный вызов функции, добавляющей вещи по ходу. Каждый вызов вызывает ровно один дополнительный вызов, но только на глубину n. Потом возвращается.
Итак, у вас сложность O(n).
Но вы можете сделать еще один шаг вперед. Алгоритм fib может быть легко реализован как O(1).
Это потому, что fib быстро превосходит размер целого числа (даже long long). Вы можете легко предварительно вычислить все допустимые значения, которые могут быть сохранены в переменной, и поместить их в массив. Затем просто верните значение, просмотрев результат:
int fib(int n) {
static const int fibValue[] = { ... };
if (n < 0 || n > std::size(fibValue)) {
// This is 47 for 32 bit ints
// 93 for 64 bit ints
throw "Result out of range"
}
return fibValue[n];
}
Чтобы быть откровенным: вы \$O(n)\$вовремя и \$O(n)\$в памяти. Я не верю, что вы можете легко добиться большего успеха в целочисленной арифметике (при ее фактическом вычислении) во времени, но память может быть \$O(1)\$.
Как было указано Питером Кордесом , существует « Замкнутая форма » для последовательности Фибоначчи, что означает, что если у вас есть система с плавающей запятой бесконечной точности с постоянным временем, вы можете достичь \$O(1)\$. Компьютер с плавающей запятой может достичь приближения, но я думаю, что вы получите более точные результаты с целочисленной математикой.
Как также указал Питер Кордес , существует « метод последовательности Лукаса », который может \$O(\log{n})\$ учитывая целочисленное умножение и немного большей сложности.
Если вы используете свою функцию итеративно для печати последовательности Фибоначчи, ваш временной результат будет \$O(n^2)\$, и это можно сделать в \$O(n)\$.