我的shuffle功能有哪些缺点？ [英] What are the disadvantages of my shuffle function?

问题描述

在阅读了SO上的一些如何改组问题之后，我看到这个答案被普遍接受：

After reading through some "how to shuffle" questions on SO, I saw that this answer was generally accepted:

function shuffle (array) {
    var tmp, current, top = array.length;

    if(top) while(--top) {
        current = Math.floor(Math.random() * (top + 1));
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
    }

    return array;
}

但是随机选择列表中的元素会出现什么问题， 就像我发布的那样：

But what would the problems be with just picking the elements in the list randomly, like I posted:

function shuffle (array) {
  var result = [];
  while(array.length){
    var index = Math.floor(Math.random() * array.length);
    result.push(array.splice(index, 1)[0]);
  }  
  return result;
}

推荐答案

你的答案给出的结果似乎没有任何问题，当你拿起一个随机索引，然后将它推送到结果数组时，它确实似乎在洗牌。

There doesn't seem to be anything wrong with the result given by your answer, it does seem to shuffle the array as you pick up a random index and then push it to the resulting array.

两种方法之间的区别在于效率，第一种解决方案的最坏情况时间复杂度为O（n），并且您的解决方案的最坏情况时间复杂度为O（n ^ 2），因为拼接有O（n）的最坏情况复杂度，并且有一个while循环取O（n），第二种方法的空间复杂度为O（n）。

The difference between the two approaches is of efficiency, the first solution has a worst case time complexity of O(n) and your solution has a worst case time complexity of O(n^2) as splice has a worst case complexity of O(n) and there is a while loop taking O(n), also the second approach has a space complexity of O(n).

这篇关于我的shuffle功能有哪些缺点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！