0

我已经编写了如下代码，但我对这个算法的复杂度是 O(n) 还是 O(n 2 ) 感到困惑。任何机构都可以确认我吗？

  for(int i=0, j=i+1;i<array.length;j++)
    {

        if(j==array.length)
        {
            if(array[i]==3)
                System.out.println(array[i]);
            i++;                
            j=i;
            continue;
        }

        int k=array[i]+array[j];
        if(k==3)
        {
            System.out.println("{"+array[i]+","+array[j]+"}");
        }

    }
4

5 回答 5

4

唯一重要的部分是：

for (int i=0, j=i+1; i < array.length; j++)
{
    if (j == array.length)
    {
        ...
        i++;                
        j=i;
        continue;
    }
 ...
 }

循环正在运行j = i+1to j == array.length; theni递增并j重复循环。

因此这是一个 O(n 2 ) 算法。

于 2013-07-28T13:19:40.250 回答
2

它是 O(n^2)，

i = 0;
    j = 1;==>j =array.length.
i = 1;
    j = 1;==>j =array.length.
i = 2;
    j = 2;==>j =array.length.
...
i = n;
    j = n;==>j =array.length.
...
i = array.length;
    j =array.length.

因此，循环运行n(n-1)/2 次。它是 O(n^2)。

下面这也是一个 O(n^2) ：

for(i=0;i<n;++i)
{
    for(j = 0; j<n;++j)
    {
        if(...)
           ...
        else
           ...
        ...  
    }
}
于 2013-07-28T13:18:47.663 回答
2

是的O(n^2)。只有在遍历整个数组i后才会增加。j这发生在循环的每次迭代中，每次迭代输入变小 1。所以n*(n-1)/2次，即O(n^2)。

于 2013-07-28T13:24:27.873 回答
2

是O(n^2)。

从i=0: for j = 1 -> array.length => n interations开始

第 2 步：i = 1 => for j = 2 -> array.length => n - 1 次迭代

...

步骤 n - 1： i = array.length - 2 => for j = array.length - 1 -> array.length => 1 次迭代

因此，复杂度为n * (n + 1) / 2，即n^2。

于 2013-07-28T13:27:58.353 回答
1

这是 O((n(n+1))/2)

这是 O(n^2)

于 2013-07-28T13:23:33.807 回答