java—内部循环从实际索引的第一个循环开始的2个循环的复杂度是多少？

gzjq41n4 于 2021-06-30 发布在 Java

关注(0)|答案(1)|浏览(300)

互联网上的人们，
我在研究算法和它们的复杂性，我写了一个“天真”的代码来寻找数组中的倒数。首先，这看起来很简单，然后我开始怀疑j=i+i是否会将第二个循环的复杂度从最坏情况下的o（n）更改为更低的值？
以下是我用java编写的代码：

public static void naiveInversionCount(int[] T){
    int count = 0;
    for(int i = 0; i < T.length -1; i++){ // O(n)
        for(int j = i+1; j < T.length; j++){ // O(n) ???
            if(T[i]> T[j]) count++; // O(1)
        }
    }
    System.out.println("Naive method returns : " + count);
}

非常感谢你

Java sorting Algorithm complexity-theory time-complexity

来源：https://stackoverflow.com/questions/65379393/what-is-the-complexity-of-2-loops-with-the-inside-loop-starting-at-the-first-one