java - 这种循环的复杂性是什么？

Question

能否请您帮我澄清一下以下代码的复杂性，我在每一步中遍历数组中的“未访问”项目？

final int[] arr = {...};
for (int i = 0, length = arr.length; i < length; i++) {
    System.out.print(arr[i]);
    for (int j = i + 1; j < length; j++) {
        System.out.print(arr[j]);
    }
}

我打赌它是O(NlogN) 或O(N√N)，其中N 是arr.length

我说的对吗？你能解释一下为什么吗？

我认为它是 O(NlogN) 或 O(N√N) 因为在每一步中“未访问”部分都减少了所以它小于 O (N^2) 但仍大于 O(N)

Answer 1

我认为您的例程会打印如下内容:

arr[0] arr[1] arr[2] ... arr[n]
arr[1] arr[2] arr[3] ... arr[n]
...
arr[n]

如果每一步的计算都是打印，那么我会说复杂度是O(n^2)。因为所有打印的数量是(length+1)*length/2。