Una serie de Fibonacci -- ++ campo con beginner campo con fibonacci-sequence camp codereview Relacionados El problema

A Fibonacci series


6
vote

problema

Español

Tengo problemas con el análisis de tiempo y complejidad. He hecho una serie de Fibonacci de una manera recursiva. Creo que es O (n 2 ) . ¿Puedes averiguar el análisis de tiempo? Si es posible, ¿podría elaborarlo?

  #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; }   
Original en ingles

I am having trouble with time and complexity analysis. I have done a fibonacci series in a recursive way. I think it is O(n2). Can you find out the time analysis? If possible, could you elaborate it?

#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; } 
        
         
         

Lista de respuestas

7
 
vote
vote
La mejor respuesta
 

No estoy seguro de que ninguna de las respuestas todavía se haya abordado realmente la complejidad. Voy a hacer eso transformando su algoritmo en uno que sea más sencillo sin cambiar la complejidad del tiempo. Esto demuestra la complejidad del tiempo y también le brinda una versión del algoritmo que podría ser más fácil de leer y razonar.

Vamos a empezar con su solución

  extern6  

El extern7 no es realmente necesario, por lo que eliminemos eso y también deshágase de los comandos superfluos 998877766555443318 . [Vea los comentarios para la discusión de por qué este paso no es tan inocente como parece.]

  extern9  

Invierta el inline0 . También voy a volver a poner uno de esos inline1 S y tomar la impresión del inline2 parte.

  inline3  

Aplicar la optimización de la recursión de la cola --- es decir, reemplazar la llamada recursiva y la siguiente devolución con una reasignación de los parámetros y un salto al inicio de la subrutina. Este paso cambiará la complejidad del espacio, * pero no la complejidad del tiempo.

  inline4  

Use un bucle en lugar de un inline5 .

  inline6  

Realmente no necesita los parámetros para que sean parámetros. Probablemente documentaría la subrutina, por lo que está claro lo que hace. Y documentaría el bucle while with un invariante, por lo que es más claro cómo funciona.

  inline7  

(y también cambia el lugar donde se llama, curso.)

En este punto, está claro (creo) que el algoritmo es O (N). Ninguna de las transformaciones cambia la complejidad del tiempo, por lo que la complejidad del tiempo del original también es O (N).

(*) es decir, cambiará la complejidad del espacio de O (N) a O (1) a menos que su compilador haga la optimización de la recursión de cola. Si lo hace, la complejidad del espacio fue O (1) desde el inicio.

 

I'm not sure any of the answers have yet really addressed the complexity. I'm going to do that by transforming your algorithm into one that is simpler without changing the time complexity. This both proves the time complexity and also gives you a version of the algorithm that might be easier to read and reason about.

Let's start with your solution

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; } 

The else if part isn't really needed, so let's delete that and also get rid of the superfluous return commands. [See the comments for discussion of why this step isn't quite as innocent as it seems.]

void fibonacci(int n,int n1,int n2) {     if(n==0) {         cout<<endl<<n1; }     else {          fibonacci(n-1,n2,n1+n2); } } 

Reverse the if. Also I'm going to put back one of those returns and take the printing out of the else part.

void fibonacci(int n,int n1,int n2) {     if(n!=0) {         fibonacci(n-1,n2,n1+n2);         return ; }     cout<<endl<<n1; } 

Apply tail recursion optimization --- i.e., replace the recursive call and the following return with a reassignment of the parameters and a jump to the start of the subroutine. This step will change the space complexity,* but not the time complexity.

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 a loop instead of a 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; } 

You don't really need the parameters to be parameters. I'd probably document the subroutine, so it's clear what it does. And I'd document the while loop with an invariant, so it's more clear how it works.

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; } 

(And also change the place where it's called, course.)

At this point, it's clear (I think) that the algorithm is O(n). None of the transformations change the time complexity, so the time complexity of the original is also O(n).

(*) That is, it will change the space complexity from O(n) to O(1) unless your compiler does tail-recursion optimization. If it does, the space complexity was O(1) from the start.

 
 
       
       
14
 
vote

Acerca de using namespace std

Debe intentar evitar esta declaración, ya que se considera mala práctica . Es mejor evitarlo siempre que puedas. Aquí hay un ejemplo simple por qué.

  9988776655544331  

Otro problema es que si tiene esto en cualquier de los archivos de encabezado en su proyecto, se verá obligado a usar esto en cualquier archivo que haya incluido el encabezado.

¿Por qué usar el espacio de nombres STD consideró mala práctica? a>

Meta-programación de plantillas

Esto mueve el cálculo de tiempo de ejecución a Tiempo de compilación . Su programa tomará un poco más de tiempo para compilar, pero la complejidad será 9988777665544332 . Utiliza Plantillas en C ++ para forzar al compilador para calcular el valor.

Esta es otra opción para abordar este problema y la forma más rápida ya que esto mueve el cálculo a Tiempo de compilación .

Sin embargo, el inconveniente es que no puede usar valores que no se conocen en el tiempo de compilación. Por ejemplo, puede encontrar el valor para 5 pero no algo que ingresará el usuario, o por ejemplo un número aleatorio generado.

  #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á el más rápido, pero solo funcionará si sus números son constantes.
plantilla meta-programación en C ++

Reemplace la recursión con la iteración

Aunque la recursión hace que su código sea un poco más limpio, la recursión casi siempre se ejecuta más lento , esto se debe a que para cada llamada necesita una asignación de un nuevo marco de pila
Debido al hecho de que el espacio en la pila es Finita , hay un límite a la cantidad de llamadas recursivas que puede hacer, antes de que C ++ le dé 99887776655443355 . Que es desbordamiento de pila
Con unas pocas líneas de código más, puede reemplazar la recursión con este escenario y hacerlo mucho más rápido, sin este problema.
Esto no significa que no debe usar la recursión, algunos algoritmos necesitan recursión, pero si usted puede reemplazarlo con la iteración, entonces vale la pena.

Aquí está con la iteración.

  9988776655544336  

' ' sobre std::endl

' '9 y #include <iostream> #inlcude <list> using namespace std; class list // uh-hoh, list is already defined, or is that std::list? { ... }; 0 lo logrará, sino #include <iostream> #inlcude <list> using namespace std; class list // uh-hoh, list is already defined, or is that std::list? { ... }; 1 Llamadas #include <iostream> #inlcude <list> using namespace std; class list // uh-hoh, list is already defined, or is that std::list? { ... }; 2 Cada vez y enjuaga la corriente Por eso será más lento, que simplemente imprimiendo #include <iostream> #inlcude <list> using namespace std; class list // uh-hoh, list is already defined, or is that std::list? { ... }; 3

comparación entre std :: endl y ' n'

 

About using namespace std

You should try to avoid this statement as it is considered bad practice. It is best to avoid it whenever you can. Here is a simple example why.

#include <iostream> #inlcude <list>  using namespace std;  class list // uh-hoh, list is already defined, or is that std::list? {          ... };  

Another problem is that if you have this in any of the header files in your project, you will be forced to use this in any file you have included the header.

Why is using namespace std considered bad practice

Template meta-programming

This moves the calculation from run-time to compile-time. Your program will take a little longer to compile, but the complexity will be O(1). It uses templates in C++ to force the compiler to calculate the value.

This is another option to approach this problem and the fastest way since this moves calculation to compile time.

However, the drawback is that you cannot use values that aren't known at compile time. For example, you could find the value for 5 but not something the user will enter, or for example a random number generated.

#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; } 

This method will be the fastest but will only work if your numbers are constant.
Template meta-programming in C++

Replace recursion with iteration

Although recursion makes your code a little cleaner, recursion almost always runs slower, this is because for each call it needs allocation of a new stack frame
Due to the fact that space in the stack is finite, there is a limit to how many recursive calls you can make, before C++ gives you 0xC00000FD. Which is stack overflow
With a few more lines of code, you can replace recursion with this scenario and make it much faster, without this problem.
This doesn't mean that you shouldn't use recursion, some algorithms need recursion, but if you can replace it with iteration, then it's worth.

Here it is with iteration.

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' over std::endl

'\n' and std::endl will both accomplish your task, but std::endl calls std::flush every time and flushes the stream, this is why it will be slower, than simply printing '\n'

Comparison between std::endl and '\n'

 
 
         
         
7
 
vote

La forma más obvia de escribir FIB:

  int fib(int n) {     if (n < 2) // 0 or 1     {         return 1;     }     return fib(n-1) + fib(n-2); }   

Puede verlo explota porque para cada llamada a FIB () obtiene 2 llamadas posteriores, las dos llamadas obtienen 2 llamadas, obtenga 2 llamadas, 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   

Entonces, la complejidad de FIB es FIB !!!!!
Más EXACTAMENTE COMPLETY ES O(2Fib(n)-1)
Pero eliminando las constantes O(Fib(n))

Permite escribir un código para validar esto:

  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. }   

Si seguimos esto:

  int main() {     for(int loop = 2; loop < 15; ++loop)     {         std::cout << loop << " " << fib(loop) << " " << fibComplexity(loop) << " ";     } }   

genera: (formato añadido)

  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   

Pero cada curso de codificación que toma, le pedirá que haga una solución lineal a base.

Lo que presenta anteriormente es una solución recursiva (pero lineal). La mayoría de las personas habrían ido a una solución lineal basada en bucle (pero no hay diferencia). La complejidad es exactamente la misma.

Lo que has hecho es recursivamente la función que agrega las cosas a medida que avanza. Cada llamada hace exactamente una llamada adicionalmente, pero solo a una profundidad de n. Luego vuelve.

Para que tenga complejidad de O(n) .


Pero puedes llevar este paso más allá. El algoritmo de FIB se puede implementar fácilmente como O(1) .

Esto se debe a que BIB rompa rápidamente el tamaño de un entero (incluso largo y largo). Puede precalcular fácilmente los valores válidos que se pueden almacenar en una variable y ponerlos en una matriz. Luego simplemente devuelva el valor buscando el 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]; }   
 

The most obvious way to write fib:

int fib(int n) {     if (n < 2) // 0 or 1     {         return 1;     }     return fib(n-1) + fib(n-2); } 

You can see it explodes because for every call to fib() you get 2 subsequent calls which both get 2 calls with all get 2 calls 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 

So the complexity of Fib is Fib!!!!!
More exactly Complecity is O(2Fib(n)-1)
but removing constants O(Fib(n))

Lets write some code to validate this:

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. } 

If we runt this:

int main() {     for(int loop = 2; loop < 15; ++loop)     {         std::cout << loop << " " << fib(loop) << " " << fibComplexity(loop) << "\n";     } } 

Generates: ( added formatting)

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 

But every coding course you take will then ask you to make a linear based solution.

What you present above is a recursive (but linear solution). Most people would have gone for a loop based linear solution (but there is no difference). The complexity is exactly the same.

What you done is recursively call the function adding things up as you go. Each call makes exactly one additionally call but only to a depth of n. Then it returns.

So you have complexity of O(n).


But you can take this one step further. The fib algorithm can easily be implemented as O(1).

This is because fib quickly outstrips the size of an integer (even long long). You can easily pre-calulcate all the valid values that can be stored in a variable and put them in an array. Then simply return the value by looking up the result:

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]; } 
 
 
 
 
3
 
vote

Solo para ser explícito: usted es $ O (n) $ en el tiempo y $ O (n) $ en la memoria. No creo que pueda hacerlo fácilmente en una aritmética entera (cuando realmente lo calcule) a tiempo, pero la memoria podría ser $ O (1) $ . < / p>

Como se ha señalado por Peter CORDES , hay un " forma cerrada " para la secuencia Fibonacci, lo que significa que si tiene un sistema de punto flotante de precisión infinito constante. , puede lograr $ o (1) $ . El punto flotante de la computadora puede lograr una aproximación, pero creo que obtendrás resultados más precisos con Matemáticas enteras.

Como también se señaló por Peter CORDES , hay un "lucas Método de secuencia "que puede hacer $ O ( log {n}) $ Dado entero Multiplicación y un poco más complejidad.

Si usa su función Iterativamente para imprimir la secuencia FIBONACCI, su resultado de tiempo sería $ O (n ^ 2) $ , y eso se puede hacer en $ o (n) $ .

 

Just to be explicit: You are \$O(n)\$ in time and \$O(n)\$ in memory. I don't believe you can easily do better in integer arithmetic (when actually calculating it) in time, but memory could be \$O(1)\$.

As has been pointed out by Peter Cordes, there is a "Closed form" for the Fibonacci sequence, which means that if you have a constant time infinite precision floating point system, you can achieve \$O(1)\$. Computer floating point can achieve an approximation, but I think you will get more accurate results with integer math.

As also pointed out by Peter Cordes, there is a "Lucas sequence method" that can do \$O(\log{n})\$ given integer multiplication and a fair bit more complexity.

If you use your function iteratively to print the Fibonacci sequence, your time result would be \$O(n^2)\$, and that can be done in \$O(n)\$.

 
 
 
 

Relacionados problema

20  Proyecto EULER # 2 (incluso números de Fibonacci) en Swift  ( Project euler 2 even fibonacci numbers in swift ) 
Pensé que el trabajo a través de Project Euler Problemas en Swift sería una buena manera de aprender cualquier consejo o trucos. Por ejemplo, las tuplas son a...

7  Implementar una secuencia de Fibonacci genérica en óxido sin usar copia rasgo  ( Implement a generic fibonacci sequence in rust without using copy trait ) 
Estoy tratando de aprender a óxido y soy un principiante. ¿Cómo se hace frente a la implementación de una versión genérica de la secuencia FIBONACCI sin usar ...

4  Ruby Fibonacci (n) Cálculo recursivo optimizado con la reflexión  ( Ruby fibonaccin recursive computation optimized with reflection ) 
La idea es tomar el método recursivo de FibonAcci (N) conocido (y terriblemente malo): # recursively computate fibonacci(n) def fib(n) n <= 2 ? 1 : fib(n...

7  Calcular Fibonacci en O (log n)  ( Calculate fibonacci in olog n ) 
Este programa calcula el número de $ N $ TH FIBONACCI, en el tiempo $ O ( log n) $. Estoy buscando revisión de código, optimizaciones y mejores prácticas....

3  Euler 2: Fibonacci simple  ( Euler 2 simple fibonacci ) 
Estoy empezando a experimentar con F # (desde un fondo C #). Creo que estoy empezando a entrar en la forma de pensar correcta, pero este código todavía parece...

25  Proyecto EULER PROBLEMA 2 EN COTJURE  ( Project euler problem 2 in clojure ) 
Estoy en el proceso de aprendizaje de Clojure. Soy bastante nuevo en la programación funcional y me gustaría saber si mi código huele o si hay alguna implicac...

12  Proyecto EULER # 2 Incluso números de Fibonacci  ( Project euler 2 even fibonacci numbers ) 
Problema: Se genera cada nuevo término en la secuencia Fibonacci al agregar el Dos términos anteriores. Al comenzar con 1 y 2, los primeros 10 términos s...

3  Implementar el rango de Fibonacci  ( Implement fibonacci range ) 
Estoy implementando una gama FIBONACCI en C ++ 17 de tal manera que admite #include "fib.h" #include <iostream> int main() { for (int x : Fibonacci())...

7  Terminando un bucle C cuando se alcanza el límite máximo de hardware  ( Terminating a c loop when maximum hardware limit reached ) 
en Respuesta a la pregunta C: f & gt; 0 vs perl: $ f & gt; 0? , el uso El desbordamiento para terminar el bucle se conoce como "práctica de programación ...

6  Calculadora de secuencia N-Bonnaci  ( N bonnaci sequence calculator ) 
El código calcula una secuencia N-Bonnaci a un cierto número, según la entrada del usuario. A continuación, puede imprimirlo a un archivo y / o imprimirlo en ...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos