2010/3/4 Pablo Angulo <[email protected]>:
> 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
[email protected]
http://mail.python.org/mailman/listinfo/python-es
FAQ: http://python-es-faq.wikidot.com/
