寻找大 O 复杂度。三种算法

Question

我试图找到以下算法的时间复杂度。从我可以看到 alg1 中的前两个循环是n^2但是我不确定 alg2 中的循环的运行时间是多少。public class algo {public static int alg1(int[] A, int n) {    int l = 0;    for (int i = 0; i <= n-1; i++) {        for (int j = i+1; j <= n-1 ; j++) {           if(alg2(A,i,j) && j-i > l) {               l = j-i+1;           }        }    }    return l;}private static boolean alg2(int[] A,int i, int j) {    if(i==j) {        return true;    }    for (int k = i; k <= j-1; k++) {        if(A[k] != A[k+1]) {            return false;        }    }    return true;}}

Answer 1

您是正确的，第一个 Alg1 的时间复杂度为 O(n^2)。第二个函数 Alg2 的时间复杂度为 O(n)，因为算法的性能将与其输入大小成正比线性增长。您只有一个 for 循环，并且您没有在该代码的任何地方应用 D&C 技术。

Answer 2

alg2是 O(n)

alg1因为它alg2在内部 for 循环内所以它应该是 O(n^2 * n) = O(n^3)。如果你想证明：