申論題 - 阿摩線上測驗

申論題資訊

試卷：104年 - 104 一般警察特種考試_二等_刑事警察人員犯罪分析組：計算機概論（包括計算機結構、資料結構、程式設計）#25599
科目：計算機概論
年份：104年
排序：0

題組內容

四、下列 C 語言函數是氣泡排序演算法

申論題內容

⑴請問其時間複雜度為何？（5 分）

詳解 (共 1 筆)

詳解提供者：hchungw

圖片中的 C 語言函數實現的是氣泡排序演算法。氣泡排序的最壞情況和平均情況的時間複雜度通常是 O(n2)。這是因為該演算法包含了一個嵌套迴圈：外迴圈運行 n−1 次，內迴圈在每次外迴圈迭代時最多運行 n−i 次，其中 i 是外迴圈的當前迭代次數。當數組需要進行大量排序時，這會導致二次方數量級的比較和潛在交換次數，因此複雜度為 O(n2)。最佳情況的時間複雜度是 O(n)，當數組已經有序時會出現這種情況，因為不會進行交換，演算法可以被優化以提前停止。