java - 计算算法的复杂度 - BigO

Question

我目前正在努力解决算法问题。但我想我仍然不完全理解如何计算算法复杂度。我会说我的代码具有 O(n^3) 的复杂性，因为它们内部有三个主要循环在数据集上工作，有人可以确认这一点，或者如果我错了，请告诉我这段代码应该如何计算？

public class BigOhN3 {

private Integer[] result;
private long time;


BigOhN3(Integer[] list) {
    long start = System.currentTimeMillis();
    int coefficientSum = calculateCoefficient(list);
    result = new Integer[list.length];

    //Main loop
    for(int i = 0; i < list.length; i++) {
        int coefficientSumIndexI = coefficientSum;
        for(int j = 0; j < list.length; j++) {
            Integer[] listIndexJ = list.clone();
            if(j == i && j < list.length - 1) {
                j++;
            }
            int a = listIndexJ[i];
            int b = listIndexJ[j];
            listIndexJ[i] = b;
            listIndexJ[j] = a;
            int coefficientSumIndexJ = calculateCoefficient(listIndexJ);
            if(coefficientSumIndexJ < coefficientSumIndexI) {
                coefficientSumIndexI = coefficientSumIndexJ;
                result[i] = coefficientSumIndexJ;
            }
        }
        if(result[i] == null) {
            result[i] = coefficientSum;
        }
    }
    time = System.currentTimeMillis() - start;
}

public long getTime() {
    return time;
}

private int calculateCoefficient(Integer[] list) {
    int sum = 0;
    for(int i = 0; i < list.length - 1; i++) {
        int item = list[i] - list[i + 1];
        if(item < 0) {
            item = item * (-1);
        }
        sum = sum + item;
    }
    return sum;
}

Integer[] getResult() {
    return result;
}
}

Answer 1

确实是O(n^3)。但即使没有最内层循环，也将是 O(n^3)，因为克隆一个列表(实际上是一个数组)至少需要 O(n)因为您至少需要阅读所有元素。这意味着，算法的复杂度是:

O(n)*O(n)*(O(n)+O(n)) = O(n^3)

n次执行循环a.
每次执行a，执行循环b n次。
对于 b 的每次执行，复制一个采用 O(n) 的数组并运行执行 n 次的第三个循环。