求助，关于算法的时间复杂度问题?该怎么去运用呢

Question

public static void xxxx(int [] a)
for (int i = 0; i < a.length - 1; i++) {
int posMin = i;
for (int k = i + 1; k < a.length; k++) {
if (a[posMin] > a[k]) posMin = k;
}
if (posMin != i) swap(a, i, posMin);
}
}
请问一下这个算法的时间复杂度是多少? 每一个循环分别是多少? 并且说一下为什么..谢谢!!

Answer 1

这个算法的时间复杂度是O(a.length^2)当i = 0；子循环执行a.length-1当i = 1；子循环执行a.length-1-1当i = j；子循环执行a.length-1-j次依次类推把它们加起来：知这个算法的时间复杂度是O(a.length^2)

Answer 2

内循环for (int k = i + 1; k < a.length; k++) //O（N）// N=a.length;{if (a[posMin] > a[k]) //一次比较 合计 N-1次比较posMin = k; // 0 ~1 次赋值 合计 0~ N-1次赋值}外循环0~1 次交换（每个交换3次赋值） 总计1~N-1次 最差N-1次交换平均的为 O(N^2）如果，最多N-1次交换每一轮内循环，进行了N-1次比较；总的比较次数为 （N-1） *（N-1） =（N-1)^2所以为O(N^2）改进的内循环for (int k = i + 1; k < a.length; k++) //O（N）// N=a.length;{if (a[posMin] > a[k]) //一次比较 合计 N-1次比较posMin = k; // 0 ~1 次赋值 合计 0~ N-1次赋值else break;}改进的也为O(N^2),但是实际运行，比原来要快多了！因为 排好序时为O(N)，内循环，只进行一次比较；接近排好序的也要快得多，只有接近逆序的才是O(N^2)