java - 以下程序的时间复杂度是多少？

Question

如何计算以下程序的时间复杂度？

int[] vars = { 2, 4, 5, 6 };
int len = vars.length;
int[] result = new int[len];

for (int i = 0; i < len; i++) {
    int value = 1;

    for (int k = 0; k < i; k++) {
        value = value * vars[k];
    }
    for (int j = i + 1; j < len; j++) {
        value = value * vars[j];
    }

    result[i] = value;
}

上面的和下面的有什么区别？

for (int i = 0; i < len; i++) {
    int value = 1;

    for (int j = 0; j < len; j++) {
        if(j != i) {
            value = value * vars[j];
        }
    }

    result[i] = value;
}

Answer 1

i for 循环的时间复杂度为 O(n)，因为它对数组的每个元素执行一次迭代。对于数组中的每个元素，您将再次遍历它 -- 平均一半在 k for 循环中，平均一半在 j for 循环。其中每一个也是 O(n)。如果数组中有4个元素，操作次数与n*(n - 1)成正比，但在时间复杂度上，1等常量被忽略。

您的方法将执行的操作数与其中的元素数乘以自身成正比，因此，总体而言，该方法的复杂度为 O(n²)。