Open ccforward opened 8 years ago
arr 要容错,给 arr.length >>>0
第一个时间复杂度为什么是 O(n^2),应该就是 O(n),代码中也只做了一次遍历吧?
明白了 splice 的复杂度是 O(n),所以综上复杂度是 O(n^2)
第二种方式快要结束时的数字相对固定了,这样的洗牌感觉随机性不够了。
@huyansheng3 数字固定对随机性并没有什么影响呀。比如剩下 1,4,3,每个概率就是 1 / 3。肯定是等概率的呀,怎么会有随机性不够的说法。
@zyvas 是我理解有误。遍历数组,每个元素和其他 n-1中的任意交换位置,即可满足每个元素都有 1/n 的概率出现在任一位置,即是洗牌。
洗牌算法(shuffle)的js实现
Fisher-Yates
先看最经典的 Fisher-Yates 的洗牌算法
这里有一个该算法的可视化实现
其算法思想就是 从原始数组中随机抽取一个新的元素到新数组中
按步骤一步一步来就很简单的实现
这种算法要去除原数组 arr 中的元素,所以时间复杂度为 O(n2)
Knuth-Durstenfeld Shuffle
Fisher-Yates 洗牌算法的一个变种是 Knuth Shuffle
每次从未处理的数组中随机取一个元素,然后把该元素放到数组的尾部,即数组的尾部放的就是已经处理过的元素,这是一种原地打乱的算法,每个元素随机概率也相等,时间复杂度从 Fisher 算法的 O(n2)提升到了 O(n)
Durstenfeld Shuffle的算法是从数组第一个开始,和Knuth的区别是遍历的方向不同
Other
Array.sort()
利用Array的sort方法可以更简洁的实现打乱,对于数量小的数组来说足够。因为随着数组元素增加,随机性会变差。
ES6
Knuth-Durstenfeld shuffle 的 ES6 实现,代码更简洁