complejidad de algoritmos
Publicado por JoseMendez (1 intervención) el 17/08/2018 22:25:49
Saludos:
El tema es el siguiente. Sabemos que el orden de complejidad del algoritmo recursivo de la serie de Fibonacci es O(2^n) y cuyo código en C es el siguiente:
Me he dedicado a buscar una solución no recursiva para encontrar el enésimo termino de la serie, y pude encontrar una solución matemática que consiste en una ecuación en función de n (n es enésimo termino que se desea hallar de manera directa), esta es la ecuación:
((1/sqrt(5))*pow(((1+sqrt(5))/2),n))-((1/sqrt(5))*pow(((1-sqrt(5))/2),n)); para todo n=1, 2, 3, ...
La pregunta es ¿Cuál es el orden de complejidad de dicha ecuación?.
Hago esta consulta porque me confunde un poco la raíz cuadrada y por otro lado el exponente n. Y no estoy seguro si es O(n) ó O(2^n) u otro orden de complejidad.
Apelo a su ayuda compañeros del foro, y agradecería mucho me pudieran dar una manito. Estoy abierto a toda sugerencia y comentario.
Muchas gracias...
El tema es el siguiente. Sabemos que el orden de complejidad del algoritmo recursivo de la serie de Fibonacci es O(2^n) y cuyo código en C es el siguiente:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream.h>
#include<conio.h>
int fibo(int n)
{if(n==0 || n==1)
return n;
else
return (fibo(n-1) + fibo(n-2));
}void main()
{int n;
cout<<"Digita numero de termino: ";
cin>>n;
cout<<"El termino "<< n <<" es "<< fibo(n);
getch();
}Me he dedicado a buscar una solución no recursiva para encontrar el enésimo termino de la serie, y pude encontrar una solución matemática que consiste en una ecuación en función de n (n es enésimo termino que se desea hallar de manera directa), esta es la ecuación:
((1/sqrt(5))*pow(((1+sqrt(5))/2),n))-((1/sqrt(5))*pow(((1-sqrt(5))/2),n)); para todo n=1, 2, 3, ...
La pregunta es ¿Cuál es el orden de complejidad de dicha ecuación?.
Hago esta consulta porque me confunde un poco la raíz cuadrada y por otro lado el exponente n. Y no estoy seguro si es O(n) ó O(2^n) u otro orden de complejidad.
Apelo a su ayuda compañeros del foro, y agradecería mucho me pudieran dar una manito. Estoy abierto a toda sugerencia y comentario.
Muchas gracias...
Valora esta pregunta
0