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);}}請(qǐng)問一下這個(gè)算法的時(shí)間復(fù)雜度是多少? 每一個(gè)循環(huán)分別是多少? 并且說一下為什么..謝謝!!
2 回答
汪汪一只貓
TA貢獻(xiàn)1898條經(jīng)驗(yàn) 獲得超8個(gè)贊
這個(gè)算法的時(shí)間復(fù)雜度是O(a.length^2)
當(dāng)i = 0；子循環(huán)執(zhí)行a.length-1
當(dāng)i = 1；子循環(huán)執(zhí)行a.length-1-1
當(dāng)i = j；子循環(huán)執(zhí)行a.length-1-j次
依次類推把它們加起來：知這個(gè)算法的時(shí)間復(fù)雜度是O(a.length^2)
qq_笑_17
TA貢獻(xiàn)1818條經(jīng)驗(yàn) 獲得超7個(gè)贊
內(nèi)循環(huán)
for (int k = i + 1; k < a.length; k++) //O（N）// N=a.length;
{
if (a[posMin] > a[k]) //一次比較 合計(jì) N-1次比較
posMin = k; // 0 ~1 次賦值 合計(jì) 0~ N-1次賦值
}
外循環(huán)
0~1 次交換（每個(gè)交換3次賦值） 總計(jì)1~N-1次 最差N-1次交換
平均的為 O(N^2）
如果，最多N-1次交換
每一輪內(nèi)循環(huán)，進(jìn)行了N-1次比較；
總的比較次數(shù)為 （N-1） *（N-1） =（N-1)^2
所以為O(N^2）
改進(jìn)的內(nèi)循環(huán)
for (int k = i + 1; k < a.length; k++) //O（N）// N=a.length;
{
if (a[posMin] > a[k]) //一次比較 合計(jì) N-1次比較
posMin = k; // 0 ~1 次賦值 合計(jì) 0~ N-1次賦值
else break;
}
改進(jìn)的也為O(N^2),但是實(shí)際運(yùn)行，比原來要快多了！因?yàn)?排好序時(shí)為O(N)，內(nèi)循環(huán)，只進(jìn)行一次比較；接近排好序的也要快得多，只有接近逆序的才是O(N^2)
添加回答
舉報(bào)
0/150
提交
取消