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

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)