Article View: es.comp.lenguajes
Article #50Re: Solucion en lenguaje SIMPLON. Era->[Re: Muy importante]
From: Jose Luis Trivino
Date: Mon, 02 Aug 1999 00:00
Date: Mon, 02 Aug 1999 00:00
38 lines
2862 bytes
2862 bytes
Javier Cantero wrote:
> �Tres bucles anidados sobrepasa la exponencial?
>
> Lo siento, pero esto me chirr�a. Tres bucles for anidados:
Ahora mismo no recuerdo (igual hasta me he equivocado, aunque creo que
no). Estoy escribiendo estos email de memoria a partir de lo que
recuerdo de un curso de doctorado sobre teor�a de la calculabilidad. Con
mucho gusto averiguar�a realmente cuanto se puede calcular con tres
bucles, pero es que mi director de tesis, que esta mucho m�s metido en
este tema, anda de vacaciones hasta dentro de unos dias. En cualquier
caso, si lo averiguo te enviar� un email.
En cualquier caso (y aunque probablemente a mucha gente no le guste
este algoritmo), el siguiente c�digo si tiene complejidad exponencial
O(a^N) sin hacer ni siquiera uso de la multiplicaci�n:
p= 1;
for( i=0; i<N; i++ ){
for( k=0; k<a; k++ ){
p= p + p;
for( j=1; j<p; j++ ){
<sentencia repetida m�s de a^N veces>
}
}
}
Hasta m�s bits,
--
-------------------------------------------------
Jose Luis Triviño Rodriguez
Dept. Lenguajes y Ciencias de la Computaci�n
http://www.lcc.uma.es/personal/trivino/trivino.html
-------------------------------------------------
La medida de programar es programar sin medida
Technical Details
Message-ID:
<37A57E44.52C4A910@lcc.uma.es>Path:
arc1-ca.pugleaf.net!unknown!not-for-mailReferences:
<7midgc$13n@telerad.teleline.es> <7mj1oq$7jb@telerad.teleline.es> <378DCE0C.1433597D@interactivebureau.com> <Pine.LNX.4.10.9907160956530.3269-100000@golum.inforg.uniovi.es> <3792E452.5FC9ABE2@lcc.uma.es> <87g12865yb.fsf_-_@eb2ebu.ampr.org> <37A0DA94.624F5462@lcc.uma.es> <37A17DC8.1A03D66A@interactivebureau.com> <37A363FD.C569CCFE@lcc.uma.es> <slrn7q8f0m.4k.javier@eb2dsn.ampr.org>Show Full Headers
Complete Article Headers
X-Google-Language: SPANISH,ASCII X-Google-Thread: 105378,7f2767b4c9fc7a53 X-Google-Attributes: gid105378,public X-Google-Thread: 1116f3,7f2767b4c9fc7a53 X-Google-Attributes: gid1116f3,public X-Google-Thread: 10f58f,7f2767b4c9fc7a53 X-Google-Attributes: gid10f58f,public X-Google-Thread: f53ec,7f2767b4c9fc7a53 X-Google-Attributes: gidf53ec,public X-Google-Thread: f59de,7f2767b4c9fc7a53 X-Google-Attributes: gidf59de,public From: Jose Luis Trivino <trivino@lcc.uma.es> Subject: Re: Solucion en lenguaje SIMPLON. Era->[Re: Muy importante] Date: 1999/08/02 Message-ID: <37A57E44.52C4A910@lcc.uma.es> X-Deja-AN: 508304552 Content-Transfer-Encoding: 8bit References: <7midgc$13n@telerad.teleline.es> <7mj1oq$7jb@telerad.teleline.es> <378DCE0C.1433597D@interactivebureau.com> <Pine.LNX.4.10.9907160956530.3269-100000@golum.inforg.uniovi.es> <3792E452.5FC9ABE2@lcc.uma.es> <87g12865yb.fsf_-_@eb2ebu.ampr.org> <37A0DA94.624F5462@lcc.uma.es> <37A17DC8.1A03D66A@interactivebureau.com> <37A363FD.C569CCFE@lcc.uma.es> <slrn7q8f0m.4k.javier@eb2dsn.ampr.org> To: Javier Cantero <javier@eb2dsn.ampr.org> X-Accept-Language: es, en Content-Type: text/plain; charset=iso-8859-1 X-Complaints-To: news@cica.es X-Trace: mercurio.cica.es 933671890 2418 150.214.108.220 (3 Aug 1999 09:18:10 GMT) Organization: Dept. Lenguajes y Ciencias de la Computacion Mime-Version: 1.0 NNTP-Posting-Date: 3 Aug 1999 09:18:10 GMT Newsgroups: es.comp.lenguajes,es.comp.lenguajes.c,es.comp.lenguajes.c++,es.comp.lenguajes.java,es.comp.lenguajes.misc