algorithm - 这个算法的复杂度（Big O）是多少？

Question

我有一个从 0 到 n-1 的 n 个数字的数组。

int func(Integer[]array){
    int res = 0;
    for (int x = 0; x < array.length; x++) {
        for (int y = x; y > Math.max(x - 1000, 0) ; y--) {
            res = res + array[y];
        }
    }
    return res;
}

O(n), O(n^2), O(n^1/5), O(log n)

我认为是O(n^2)。我是正确的？

标签： algorithmcomplexity-theory

Answer 1

看来保罗的评论是正确的。内循环仅在恒定时间运行。因此，外部循环的时间复杂度仅为 O(N)。

该算法也在常数内存 O(1) 上运行。