javascript - 正确计算随机数生成程序(javascript)的复杂性？

Question

我正在学习一些在线算法介绍类(class)。并在一边改进我的 javascript 的同时尝试理解。我认为以下是正确的，但有什么方法可以改进吗？

function randomGenerator() {

  var x;
  var myArray = [];
  var copy = [];
  for (x = 1; x <= 10000; x += 1) {
    myArray.push(x);
  }

  var m = myArray.length;
  var i;

  while (m) {
    i = Math.floor(Math.random() * myArray.length);
    if (i in myArray) {
      copy.push(myArray[i]);
      delete myArray[i];
      m--;
    }
  }
  return copy;
}

我认为这里的复杂度是 O(n^3)，因为第一个 for 循环，接下来的 while 循环和最后的 if 语句。我的处理方式是否正确？

编辑:感谢@Dukeling，找到了更好的方法来做到这一点。

function randomGenerator() {    
var x;
var myArray = [];
var t;
for ( x = 1; x <= 10000; x+=1) {
myArray.push(x);
}

var m = myArray.length;
var i;

while (m) {
i = Math.floor(Math.random() * m-=1);

t=myArray[m];
myArray[m]=myArray[i];
myArray[i]=t;

}
return myArray;
}

现在复杂度降低到 O(n) 线性时间。 (如有错误请指正)

Answer 1

您的函数不接受任何输入，所以我假设您想要获得与您在第一个 for 中创建的数组大小相关的复杂度循环。

您不会将两个循环相乘，因为它们不是嵌套的，它们是连续的。所以复杂度是两个循环中最差的复杂度。

for循环是 O(n) 因为它只是递增 x来自 1至 10000 .

while循环更复杂。它只会递减 m当它找到随机索引 i 时在数组中。当数组大部分已满时，将找到大多数索引。但随着它变得越来越稀疏，这可能会失败更多。因此，删除下一​​个元素并递减 m 所需的迭代次数与阵列的充满程度成反比。平均需要 10000/fullness每次递减的迭代。一开始这在1附近，而最后将需要大约 10,000 次迭代。所以总时间平均值 1 + 2 + ... + n = n * (n+1)/2 .这使得 while循环 O(n²).

if()不是循环，它要么执行循环体，要么不执行循环体，所以它是 O(1)。

这使得整体复杂度为 O(n²)。