Mi chiedevo la complessità temporale di shuffle function nella libreria/modulo random Python. È O (n) o è inferiore a quello?prestazioni dell'algoritmo python shuffle
C'è un sito Web che mostra le complessità temporali delle funzioni che appartengono alle librerie Python?
Non è possibile mescolare un elenco in modo completamente casuale in meno di O (n).
Il implementation of random.shuffle() utilizza Fisher-Yates shuffle algorithm, che è facilmente visibile come O (n).
Grazie! Suppongo di aver bisogno della mia funzione casuale (non del tutto casuale, immagino) –
@Saher: puoi persino immaginare un metodo per mischiare una lista al posto che sia meglio di O (n)? – geoffspear
Non ci ho pensato, ma quello che intendevo è fondamentalmente per i miei scopi dell'algoritmo che sto scrivendo, posso solo mescolare i primi 4 o 5 elementi e scegliere il primo, non è cruciale. –
Per la tua seconda domanda - http://wiki.python.org/moin/TimeComplexity –
@Alex: considerando che l'unica libreria in quell'elenco è 'collections', non proprio quello che l'OP sta chiedendo, penso. – geoffspear
@Wooble È un wiki, quindi non può essere limitato al solo 'collections' in futuro. (Durante la rilettura, sembra che questo sia per CPython, ma almeno un riferimento interessante: può ispirare qualcuno a creare una pagina wiki equivalente per 'random' e altre librerie) –