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/

Responder a