資料結構與演算法
對於有 n 個元素的陣列，將所有不同的兩個元素組合各比較一次的處理（以雙重迴圈將第 i 個元素與其後的所有元素比較，並讓 i 逐一前進），其時間複雜度為下列何者？
- AO(n)
- BO(n log n)
- CO(n²)
查看答案與解析
正確答案：C. O(n²)
比較的組數為 (n−1) + (n−2) + … + 1 = n(n−1)/2，n = 10 時為45次，n = 1000 時為499,500次。時間複雜度的階只看 n 變大時的增加方式，因此省略係數1/2與低次項，表示為 O(n²)。n 變為2倍時，次數約變為4倍。O(n) 是每個元素只看一次的處理，O(n log n) 則是像合併排序那樣反覆對半分割的處理的複雜度。
- A. 若每個元素只看一次是 O(n)，但這裡每個元素都要與其餘所有元素比較。
- B. 這是合併排序等反覆對半分割的演算法的複雜度，比比較所有組合的處理小。
- C. 正確。比較次數為 n(n−1)/2，與 n² 成正比增加。