2010/3/4 Pablo Angulo <pablo.ang...@uam.es>: > Olemis Lang (Simelix) escribió: >> Aquí por ejemplo hay un caso que ilustra el hecho de no confiar >> demasiado en las estimaciones teóricas . Las estimaciones de Pablo et >> al se pueden ver afectadas por la eficiencia de la implementación del >> método index (el cual no me parece que sea muy O(1) que digamos, pero >> no tengo los detalles en la mano ...) . E.g. si fuera O(n), O(log(n)) >> ... en el peor caso entonces todos los análisis anteriores no serían >> del todo precisos (CMIIW) >> > > index no es O(1), sino que tarda tanto como tenga que buscar. Si tiene > que recorrer toda la lista, será O(n). En este caso, el tiempo total es > O(n) porque no se pasa dos veces por el mismo elemento de conjunto, pero > eso no significa que index sea O(1).
Si no es O(1) entonces sospecho que en {{{ #!python ultimo = -1 for v in subconjunto: ultimo = conjunto.index(v, ultimo+1) yield ultimo }}} hay un ciclo `for` explícito más un ciclo implícito `index`, lo que me hace pensar que el desempeño en el peor caso puede ser O(M * N) y en el mejor sospecho que sea O(M^2), solo que hay una realidad, el ciclo implícito es mucho más eficiente pues está implementado directamente en (C)Python CMIIW ;o) -- Regards, Olemis. Blog ES: http://simelo-es.blogspot.com/ Blog EN: http://simelo-en.blogspot.com/ Featured article: Support micro-seconds as added by Trac in revision 9210 for upcoming 0.12... - http://bitbucket.org/osimons/trac-rpc-mq/changeset/62ffe719a84a/ _______________________________________________ Python-es mailing list Python-es@python.org http://mail.python.org/mailman/listinfo/python-es FAQ: http://python-es-faq.wikidot.com/