python shuffle算法性能

Question

我想知道 shuffle function 的时间复杂度在 random Python 库/模块中。是 O(n) 还是小于它？

是否有网站显示属于 Python 库的函数的时间复杂度？

Answer 1

你不能在小于 O(n) 的时间内以完全随机的方式打乱列表。

implementation of random.shuffle()使用 Fisher-Yates shuffle algorithm ，很容易看出是 O(n)。