数组双循环中对的时间复杂度
-
29-09-2020 - |
题
我知道,以下内容是: 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
解决方案
这是众所周知的任务“检查重复”,例如,在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)$ 。
其他提示
算法的时间复杂度取决于计算模型。算法通常在RAM机器中进行分析,其中对机器字的基本操作(例如赋值、算术和比较)成本 $O(1)$. 。机器字有长度 $O(\log n)$, , 在哪里 $n$ 是输入的大小。
在你的情况下,输入的大小至少是 $n$ (定义为长度 array
), 所以 count
适合单个机器字。算法中每个基本操作的成本 $O(1)$, ,所以总体时间复杂度是 $\θ(n^2)$, ,因为该算法执行了这么多基本操作。