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

Question

你能帮我澄清一下我在每一步遍历数组中的 "unvisited" 项的下面这段代码的复杂性吗？

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) 因为在每一步中 "unvisited" 部分都会减少所以它小于 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.