java - 这两个for循环的复杂度是多少？

Question

这个算法的时间复杂度是多少？我最初的猜测是 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++;
        }
    }
}

Answer 1

代码中的 if 部分执行了大约 1 + 2 + 3 +...+ n 次(n - i - 1 其中 i = 0...n - 1，等于 0,5*n*(n+1)，即 O(n^ 2)。