2010/3/4 Pablo Angulo <pablo.ang...@uam.es>:
> Olemis Lang (Simelix) escribió:
>> 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`
>
>
> No lo sospeches: tiene que haber un bucle para encontrar el índice, pero
> en cuanto encuentras el primer índice con ese valor, te sales del bucle.
> ¿Cuántas iteraciones haces del bucle en total? Bueno, puede que para
> algún caso particular hagan falta muchas iteraciones, pero la suma de
> todas las iteraciones no puede superar N: La primera iteración del bucle
> "for v in subconjunto", recorres desde 0 hasta indice[0], luego desde
> indice[1] hasta indice[2],... si sumas todas esas cantidades tienes:
>
> (indice[0] - 0) + (indice[1]-indice[0]) + ... + (indice[M-1] -
> indice[M-2]) = indice[M-1] < N
Tenía entendido que era así
indice[0] + indice[1] + ... + indice[M-1] = sum(indice[i] for i in
xrange(M)) <= N * (N + 1) / 2 - M * (M+ 1) / 2
peor caso cuando son los M últimos elementos del arreglo ;o)
No me parece que `index` recuerde el último índice de la lista (no
estamos hablando de iteradores ;o) entre dos llamadas diferentes para
recomenzar la búsqueda de un nuevo elemento (¿ o es que funciona así
internamente ?) ... Quizás es que no comprendí la parte del `-
indice[0]` ... `- indice[M - 1]`
La solución que presenté antes basada en itertools.count si funciona
apróximadamente como se describe acá y por tanto resulta O(N) en el
peor caso
;o)
--
Regards,
Olemis.
Blog ES: http://simelo-es.blogspot.com/
Blog EN: http://simelo-en.blogspot.com/
Featured article:
_______________________________________________
Python-es mailing list
Python-es@python.org
http://mail.python.org/mailman/listinfo/python-es
FAQ: http://python-es-faq.wikidot.com/
