🚀 go-pugleaf

In article <37A363FD.C569CCFE@lcc.uma.es>, Jose Luis Trivino wrote:

>Al parecer su origen esta en un articulo sobre complejidad computacional y
>calculabilidad que pretendia analizar lo que se puede calcular con programas
>con n bucles anidados. No he leido ese articulo y no os puedo dar mucha
>informaci�n, pero basicamente os puedo decir que con tres bucles for anidados
>se puede calcular casi cualquier cosa y, desde luego, la complejidad
>computacional de un programa de este tipo sobrepara la exponencial, esto es,
>da igual lo rapido que sea el ordenador, siempre podras encontrar una entrada
>para el algoritmo que haga intratable el problema.

	�Tres bucles anidados sobrepasa la exponencial?

	Lo siento, pero esto me chirr�a. Tres bucles for anidados:

	for( i = 0; i < N; i++ )
		for( j = 0; i < N; i++ )
			for( k = 0; i < N; i++ )
			{
				operacion de Orden O(1)
			}
			
	Esto es de O(N^3). Mucho m�s peque�o respecto a complejidad
computacional que por ejemplo (2^n) que es exponencial (no tienes m�s que
calcular las derivadas o graficarlas y ver como crecen cada una). De hecho,
para cualquier k,  O(n^k) < O(2^n).


                                Saludos de Javier (jcantero @ jet.es)

----
"Con Pentium III ahora s� que ser� usted un usuario REGISTRADO"