Uma série Fibonacci
Estou tendo problemas com análise de tempo e complexidade. Eu fiz uma série de Fibonacci de forma recursiva. Eu acho que é O (n 2 ) . Você pode descobrir a análise do tempo? Se possível, você poderia elaborá-lo?
#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;
}
Respostas
Não tenho certeza se alguma das respostas ainda abordou a complexidade. Vou fazer isso transformando seu algoritmo em um mais simples, sem alterar a complexidade do tempo. Isso prova a complexidade do tempo e também fornece uma versão do algoritmo que pode ser mais fácil de ler e raciocinar.
Vamos começar com sua solução
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;
}
A else ifparte não é realmente necessária, então vamos excluí-la e também nos livrar dos returncomandos supérfluos . [Veja os comentários para uma discussão sobre por que essa etapa não é tão inocente quanto parece.]
void fibonacci(int n,int n1,int n2)
{
if(n==0) {
cout<<endl<<n1; }
else {
fibonacci(n-1,n2,n1+n2); }
}
Inverta o if. Também vou colocar de volta um daqueles returne tirar a impressão da elsepeça.
void fibonacci(int n,int n1,int n2)
{
if(n!=0) {
fibonacci(n-1,n2,n1+n2);
return ; }
cout<<endl<<n1;
}
Aplicar otimização de recursão final --- isto é, substituir a chamada recursiva e o retorno seguinte por uma reatribuição dos parâmetros e um salto para o início da sub-rotina. Esta etapa mudará a complexidade do espaço, * mas não a complexidade do tempo.
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;
}
Use um loop em vez de um 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;
}
Você realmente não precisa que os parâmetros sejam parâmetros. Eu provavelmente documentaria a sub-rotina, então está claro o que ela faz. E eu documentaria o loop while com um invariante, então fica mais claro como funciona.
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;
}
(E também mude o lugar onde é chamado, claro.)
Neste ponto, está claro (eu acho) que o algoritmo é O (n). Nenhuma das transformações altera a complexidade do tempo, então a complexidade do tempo do original também é O (n).
(*) Ou seja, ele mudará a complexidade do espaço de O (n) para O (1), a menos que seu compilador faça otimização de recursão de cauda. Em caso afirmativo, a complexidade do espaço era O (1) desde o início.
Sobre using namespace std
Você deve tentar evitar essa afirmação, pois é considerada uma prática ruim . É melhor evitá-lo sempre que puder. Aqui está um exemplo simples do porquê.
#include <iostream>
#inlcude <list>
using namespace std;
class list // uh-hoh, list is already defined, or is that std::list?
{
...
};
Outro problema é que, se você tiver isso em qualquer um dos arquivos de cabeçalho do seu projeto, será forçado a usá-lo em qualquer arquivo que incluiu o cabeçalho.
Por que usar o namespace std é considerado uma prática ruim
Meta-programação de template
Isso move o cálculo do tempo de execução para o tempo de compilação . Seu programa demorará um pouco mais para compilar, mas a complexidade será O(1). Ele usa modelos em C ++ para forçar o compilador a calcular o valor.
Esta é outra opção para abordar este problema e a maneira mais rápida, pois move o cálculo para o tempo de compilação .
No entanto, a desvantagem é que você não pode usar valores que não são conhecidos em tempo de compilação. Por exemplo, você pode encontrar o valor, 5mas não algo que o usuário irá inserir ou, por exemplo, um número aleatório gerado.
#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;
}
Este método será o mais rápido, mas só funcionará se seus números forem constantes.
Meta-programação de template em C ++
Substitua recursão por iteração
Embora a recursão torne seu código um pouco mais limpo, a recursão quase sempre é executada mais lentamente , porque para cada chamada ela precisa de alocação de um novo quadro de pilha.
Devido ao fato de que o espaço na pilha é finito , há um limite para quantas chamadas recursivas você pode fazer, antes que C ++ lhe dê 0xC00000FD. Que é o estouro de pilha.
Com mais algumas linhas de código, você pode substituir a recursão por este cenário e torná-lo muito mais rápido, sem esse problema.
Isso não significa que você não deve usar recursão, alguns algoritmos precisam de recursão, mas se você puder substituí-la por iteração, então vale a pena.
Aqui está com iteração.
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' sobre std::endl
'\n'e std::endlambos realizarão sua tarefa, mas std::endlchama std::flushtodas as vezes e libera o fluxo, é por isso que será mais lento do que simplesmente imprimir'\n'
Comparação entre std :: endl e '\ n'
A maneira mais óbvia de escrever mentiras:
int fib(int n)
{
if (n < 2) // 0 or 1
{
return 1;
}
return fib(n-1) + fib(n-2);
}
Você pode ver que ele explode porque para cada chamada para fib () você recebe 2 chamadas subsequentes, ambas recebem 2 chamadas e todas recebem 2 chamadas etc.
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
Então a complexidade do Fib é Fib !!!!!
Mais exatamente, Complecidade é O(2Fib(n)-1)
apenas remover constantesO(Fib(n))
Vamos escrever um código para validar isso:
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.
}
Se executarmos isto:
int main()
{
for(int loop = 2; loop < 15; ++loop)
{
std::cout << loop << " " << fib(loop) << " " << fibComplexity(loop) << "\n";
}
}
Gera: (formatação adicionada)
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
Mas cada curso de codificação que você fizer irá pedir-lhe para fazer uma solução baseada em linear.
O que você apresenta acima é uma solução recursiva (mas linear). A maioria das pessoas teria optado por uma solução linear baseada em loop (mas não há diferença). A complexidade é exatamente a mesma.
O que você fez foi chamar recursivamente a função adicionando coisas conforme você avança. Cada chamada faz exatamente uma chamada adicional, mas apenas até uma profundidade de n. Em seguida, ele retorna.
Então você tem complexidade de O(n).
Mas você pode dar um passo adiante. O algoritmo fib pode ser facilmente implementado como O(1).
Isso ocorre porque fib ultrapassa rapidamente o tamanho de um inteiro (mesmo muito longo). Você pode pré-calcular facilmente todos os valores válidos que podem ser armazenados em uma variável e colocá-los em uma matriz. Em seguida, basta retornar o valor procurando o resultado:
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];
}
Só para ser explícito: você é \$O(n)\$no tempo e \$O(n)\$em memória. Eu não acredito que você pode facilmente fazer melhor em aritmética inteira (quando, na verdade, calculando-o) com o tempo, mas a memória pode ser \$O(1)\$.
Como foi apontado por Peter Cordes , existe uma " forma fechada " para a sequência de Fibonacci, o que significa que se você tiver um sistema de ponto flutuante de precisão infinita de tempo constante, poderá obter \$O(1)\$. O ponto flutuante do computador pode fazer uma aproximação, mas acho que você obterá resultados mais precisos com a matemática de inteiros.
Como também apontado por Peter Cordes , existe um " método de sequência de Lucas " que pode fazer \$O(\log{n})\$ dada multiplicação de inteiros e um pouco mais de complexidade.
Se você usar sua função iterativamente para imprimir a sequência de Fibonacci, seu resultado de tempo seria \$O(n^2)\$, e isso pode ser feito em \$O(n)\$.