正确计算随机数生成程序的复杂度（javascript）？

Question

我正在学习一些在线算法入门课程。一边努力理解一边改进我的 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 循环更复杂。它仅在找到数组中的随机索引 i 时递减 m。当数组大部分已满时，将找到大多数索引。但随着它变得越来越稀疏，这可能会失败更多。因此，删除下一个元素并递减 m 所需的迭代次数与数组的填充程度成反比。平均而言，每次递减需要 10000/fullness 次迭代。开始时这接近 1，而最后将需要大约 10,000 次迭代。所以总时间平均 1 + 2 + ... + n = n * (n+1)/2。这使得 while 循环 O(n²).

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

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

正确计算随机数生成程序的复杂度（javascript）？

Correctly calculating the complexity of a random number generation program (javascript)?

javascript

algorithm

optimization

complexity-theory

asymptotic-complexity