0

这个算法的时间复杂度是多少？我最初的猜测是它是O(log[n])？

int array[] = new int[100];
int counter = 0;

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

5 回答 5

3

代码中的if部分大约执行1 + 2 + 3 +...+ n几次（n - i - 1where i = 0...n - 1，这等于0,5*n*(n+1)which is O(n^2)。

于 2013-09-15T11:41:49.923 回答
2

没有。这是O(N^2)。

在这里查看 “如何确定复杂性”下的第 4 节

于 2013-09-15T11:39:19.513 回答
0

有两种可能的答案。技术上正确的是O(1)，因为数组的长度是恒定的，所以内循环迭代的次数是恒定的。

如果我们假设数组的长度为 n，那么内循环的迭代次数为 n-1, n-2, n-3, ... , 1, 0。长度为 n 的算术级数之和，从 0 开始，是O(n^2)。

于 2013-09-15T11:42:15.713 回答
0 
The order is O(n^2).

说明：假设数组长度为 n。
然后对于第一个循环
的迭代：第二个循环将进行 n-2 次迭代。
所以总时间将是：（n-2）+（n-2）+............（n-2）//n-1次
将是：（n-1 )*(n-2)。

于 2013-09-15T13:54:08.320 回答
0

一种推断算法时间复杂度的正式方法：

在此处输入图像描述

于 2014-03-17T15:09:35.023 回答