内部循环从第一个实际索引开始的 2 个循环的复杂性是多少？
What is the complexity of 2 loops with the inside loop starting at the first ones actual index?
互联网人，
我正在研究算法及其复杂性，我编写了一个“天真的”代码来查找数组中的反转次数。首先，这看起来很容易，然后我开始怀疑 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);
}
非常感谢
外循环刚好运行 n 次。
内循环运行 n−1, n−2, …, 每个外循环 0 次。即平均n/2次。
并且 count++ 每个循环只运行一次。
因此嵌套循环运行了1·n(n/2)次，即在(n ²).
互联网人，
我正在研究算法及其复杂性，我编写了一个“天真的”代码来查找数组中的反转次数。首先，这看起来很容易，然后我开始怀疑 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);
}
非常感谢
外循环刚好运行 n 次。
内循环运行 n−1, n−2, …, 每个外循环 0 次。即平均n/2次。
并且 count++ 每个循环只运行一次。
因此嵌套循环运行了1·n(n/2)次，即在(n ²).