数组双循环中对的时间复杂度

Question

我知道，以下内容是： O(n^2),

int count = 0;
for(int i = 0; i<array.length(); i++) {
   for(int j = i+1; j<array.length(); j++) {
       if(array[i] == array[j]) {
           count = count + 1;
       }
   }
}

但是，应该像 count = count + 1; 被考虑在内？为了预测或组成复杂的时间方程，或使用总和符号，

n + n-1 + n-2 + n-3 + (…) + 1

Answer 1

这是众所周知的任务“检查重复”，例如，在Tim Rockgarden - 算法中可以找到它，算法_部分1_基础（2017）42页。让我说，如此，在这里，在书中取得最后一个索引“i”作为 $ n= $ “array.length（）”毫无意义，因为然后索引“ J“耗尽边界。但这不会影响我们的计数。

始终主要是选择计数的操作 - 此处其“count= count + 1”。显然最佳案例，即最少的操作量，是 $ 0 $ 。并且情况差错，即最大的操作量，是总和（我相应地纠正它索引“i”向上 $ n-1 $ ） $ t（n）= 1 + 2 + cdots +（n-1）=frac {n（n-1）} {2} $ （我们考虑案例 $ n \ geqslant 2 $ ）。

现在，因为 $ \ frac {n（n-1）} {2} \ leqslant \ frac {n \ cdot 2n} {2}= n ^ 2 $ ，很容易得出结论，案例 $ t（n）\ In o（n ^ 2）$ 。

Answer 2

算法的时间复杂度取决于计算模型。算法通常在RAM机器中进行分析，其中对机器字的基本操作（例如赋值、算术和比较）成本 $O(1)$. 。机器字有长度 $O(\log n)$, ， 在哪里 $n$ 是输入的大小。

在你的情况下，输入的大小至少是 $n$ （定义为长度 array）， 所以 count 适合单个机器字。算法中每个基本操作的成本 $O(1)$, ，所以总体时间复杂度是 $\θ(n^2)$, ，因为该算法执行了这么多基本操作。