Me preguntaba sobre la complejidad de tiempo de shuffle function en la biblioteca/módulo de Python random. ¿Es O (n) o es menos que eso?rendimiento de algoritmo de mezcla Python
¿Hay un sitio web que muestra las complejidades de tiempo de las funciones que pertenecen a las bibliotecas de Python?
No se puede barajar una lista de forma completamente aleatoria en menos de O (n).
El implementation of random.shuffle() usa el Fisher-Yates shuffle algorithm, que se ve fácilmente como O (n).
¡Gracias! Supongo que necesito mi propia función aleatoria (no es completamente aleatoria, supongo) –
@Saher: ¿puedes siquiera concebir un método para barajar una lista que sea mejor que O (n)? – geoffspear
No lo he pensado, pero lo que quiero decir es básicamente para mis propósitos para el algoritmo que estoy escribiendo. Puedo simplemente mezclar los primeros 4 a 5 elementos y elegir el primero, no es crucial. –
Para su segunda pregunta - http://wiki.python.org/moin/TimeComplexity –
@Alex: considerando que la única biblioteca en esa lista es 'colecciones ', no es exactamente lo que OP está pidiendo, creo. – geoffspear
@Wooble Es un wiki, por lo que puede no estar limitado a 'colecciones 'en el futuro. (Al volver a leer, parece que esto es para CPython, pero al menos como una referencia interesante. Puede inspirar a alguien a crear una página wiki equivalente para 'random', y otras bibliotecas) –