2 回答

TA貢獻1898條經驗 獲得超8個贊
這個算法的時間復雜度是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)

TA貢獻1818條經驗 獲得超7個贊
內循環
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)
添加回答
舉報