递归大O

Question

Big-O的问题我看过很多，但是我不太明白这个

我在练习一些面试题时遇到了一个我必须找出整数数组中是否存在毕达哥拉斯三元组的问题。我发现有一种简单的 O(n^3) 方法可以解决它，但我想找到一种更快的方法。

我的问题是，下面的代码是O(n^2)还是O(n^3)？我很困惑，因为即使我只有 2 个循环，但在最坏的情况下我需要经历 n 次 n^2，也就是 O(n^3).

public boolean findTriple(int[] array) {
return findT(0, array);
}

public boolean findT(int start, array) {
if(start == array.length-1) {
    return false;
}
int first = array[start];
for(int i = 0; i < array.length; i++) {
    for(int j = i+1; j < array.length; j++) {
        if(first*first == array[i]*array[i] + array[j]*array[j] ||
           array[i]*array[i] == array[j]*array[j] + first*first ||
           array[j]*array[j] == first*first + array[i]*array[i]) {
            return true;
        }
    }
}
return findT(start+1, array);
}

Answer 1

每次调用该函数时，您都会执行 O(n^2) 操作。你调用你的函数 n 次。所以总复杂度是：O(n^3)

递归大O

Big-O of recursion

c

recursion

big-o

time-complexity