这属于什么 Big(O) 复杂性？

Question

我有一个数组，我想比较元素之间的元素，但要避免多次比较它们，所以换句话说，一旦我比较数组[0]和数组[1]，我就不会'想再次比较 array[1] 和 array[0]，我最终会得到这个代码：

for(var i:int = 0; i < array.lenght; i++){

     var entity:Object = array[i];

      for(var j:int = i; j < array.lenght; j++){

          //do stuff

      }

  }

这不是O(N^2)，也许是O(logN)？。你用什么方法计算的？

Answer 1

在那种情况下，这是索引的问题。您选择元素并不是与整个数组进行比较，而是与从元素索引 + 1 开始的数组进行比较。例如（伪代码）：

var index:int = 0;
while(index < array.length - 2)//no need to run for last element
{
    var element:* = array[index];
    for(var i:int = index + 1; i < array.length; i++)
    {
        //compare element with array[i]
    }            
    index++;
}

第一次迭代将运行遍历数组 - 一个元素，但在下一个循环中它将遍历数组 - 2，依此类推，直到到达倒数第二个元素，然后退出。

Answer 2

你必须计算内部块将被执行的次数：

数组长度n，其中n =

3 => 2 + 1 = 3
4 => 3 + 2 + 1 = 6
5 => 4 + 3 + 2 + 1 = 10
6 => 5 + 4 + 3 + 2 + 1 = 15

因此对于长度为 n 的数组，它将执行内部块（通过比较或其他方式）的次数是所有小于 n 的整数的总和。事实上，有一个众所周知的公式可以对小于 n 的所有整数求和：

(n - 1) * n / 2

让我们将其扩展为以下内容：

1/2 * (n^2 - n)

所以，用大的术语来说：

你可以忽略 -n 因为当 n 很大时它给出了相对较小的变化（比如如果 n = 1000，那么 n ^ 2 就是 1000000，所以-n只是n ^ 2的0.1%，n越大影响越小）。这使我们得出以下结论：

1/2 * (n ^ 2)
传统上在大 O 符号中忽略常量（因为它不影响我们需要测量的增长率），所以现在我们只有 n ^ 2

所以答案是O(n^2)

这属于什么 Big(O) 复杂性？

What Big(O) complexity this belongs to?

performance

big-o

actionscript-3