C/Visual C - Orden de una funcion

   
Vista:

Orden de una funcion

Publicado por Jhonny (10 intervenciones) el 03/08/2016 15:54:58
Hola amigos, tengo la siguiente funcion, a la cual le tengo que calcular el orden de complejidad, pero no estoy seguro de si es orden n^2
Esta es la funcion
1
2
3
4
5
6
7
8
9
int bomb (int Y){
	int y = 0 ;
	for ( int i =0; i<Y;++ i ){
		for ( int j=i ; j >=0;--j ){
			y++;
		}
	}
	return y ;
}

Cualquier ayuda que me podais dar os agradeceré
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder
Imágen de perfil de Aaón Castillo

Orden de una funcion

Publicado por Aaón Castillo (8 intervenciones) el 03/08/2016 21:30:35
En efecto es de O(n^2).

La razón es la siguiente:

Primero debes tener en cuenta que por cada valor de " i " en el ciclo anidado correspondiente a " j " la variable "y" se incrementa "i + 1" veces.

Suponiendo que Y = 3:

Si i = 0 -> se hace 1 incremento porque el rango va de j=0 a j >= 0.
Si i = 1 -> se hacen 2 incrementos porque el rango va de j=1 a j >= 0 .
Si i = 2 -> se hacen 3 incrementos porque el rango va de j=2 a j >= 0 .

Para saber el número total de incrementos, sumas los de todos los casos, esto es, 1 + 2 + 3 = 6 incrementos.

Generalizando el caso en que Y = N ves que por cada valor que i tome hasta N siempre habrán (i + 1) incrementos,
esto es 1 + 2 + 3 + 4 + --- + (N+1).

Tómalo como dogma de fe, pero hay un resultado en matemáticas que se conoce como la fórmula de Gauss para la suma de los N primeros números naturales, esto es:

0 + 1 + 2 + ..... + N = N * (N -1) / 2

Originalmente la fórmula empieza en 0 (hay discusiones matemáticas que tratan que las numeraciones no deberían empezar en 0 y blablabla pero por ahora eso no es importante).

Súmale un 1 a ambos lados de la ecuación y tienes que:

1 + 2 + 3 + .... + (N + 1) = (N+1)*N/2 (puedes corroborar el cálculo tú mismo).

Lo anterior significa que el número de incrementos que hagas en tu ciclo for anidado es (N+1)*N/2, donde N = Y.

Pero (N+1) * N/2 = N^2/2 + N/2 lo cual se asemeja a un polinomio de grado dos (si A = 1/2 y C = 0, te da AN^2 + AN + C), a partir de este punto se dice que F(N) = N^2/2 + N/2 pertenece a la familia de funciones de polinomios de grado dos, lo lo que es equivalente, el algoritmo es O(N^2).

Espero esto te sea útil. Estoy a tus órdenes para cualquier duda o aclaración. Saludos.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar