正确计算随机数生成程序(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(，因为第一个循环，以下循环和最终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 ² (。