寻找大 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)。如果你想证明：