此算法的复杂度（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）。我说的对吗？

Answer 1

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

该算法还在常量内存O（1）上运行。