Zastanawiam się nad złożonością czasu w shuffle function w bibliotece/module Python random. Czy to O (n) czy jest to mniej niż to?Python shuffle algorithm performance
Czy istnieje strona internetowa pokazująca złożoność czasową funkcji należących do bibliotek Python?
Nie można losowo uporządkować listy w mniej niż O (n).
Urządzenie implementation of random.shuffle() używa modelu Fisher-Yates shuffle algorithm, który łatwo można rozpoznać jako O (n).
Dziękuję! Chyba potrzebuję mojej własnej funkcji losowej (nie całkiem przypadkowej) –
@Saher: czy potrafisz wymyślić metodę przetasowania listy, która jest lepsza niż O (n)? – geoffspear
Nie myślałem, że przez to, ale to, co miałem na myśli, to zasadniczo dla moich celów dla algorytmu, który piszę, mogę po prostu przetasować pierwsze 4 do 5 pozycji i wybrać pierwszy, nie jest to kluczowe. –
Na twoje drugie pytanie - http://wiki.python.org/moin/TimeComplexity –
@Alex: biorąc pod uwagę, że jedyną biblioteką na tej liście jest 'kolekcje', nie do końca takie, o co OP jest proszony. – geoffspear
@Wooble To jest wiki, więc nie musi się ograniczać do "kolekcji" w przyszłości. (Po ponownym przeczytaniu wygląda na to, że jest to dla CPython, ale co najmniej ciekawe referencje.Może zainspirować kogoś do stworzenia odpowiednika strony wiki dla "losowych" i innych bibliotek) –