algorithm - 大O : How to determine runtime for a for loop incrementation based on outer for loop?

Question

我有以下算法，运行时复杂度为 O(N^2) 但我想更深入地了解它，而不是仅仅记住常见的运行时。

考虑到内部 for 循环中使用 i+1 分解和分析它的正确方法是什么？

void printunorderedPairs(int[] array) {
    for(int i=0; i<array.length; i++) {
        for(int j=i+1; j<array.length; j++) {
            System.out.println(array[i] + "," + array[j]);
        }
    }
}

编辑

询问如何分析特定问题

Answer 1

What would be the right approach to break it down and analyze it

拿铅笔和纸，放下一些展开的环:

     i        inner loops per i
-------------------------------
     1               length - 1  
     2               length - 2
    ..                       ..  
     k               length - k 
    ..                       ..
length - 1                    1
length                        0

现在，为了获得所需的总时间，让我们总结一下内部循环:

 (length - 1) + (length - 2) + ... + (length - k) ... + 1 + 0

它是一个等差数列，它的和是

 ((length - 1) + 0) / 2 * length == length**2 / 2 - length / 2 = O(length**2)