38.設一數值串列有 n 筆資料，若以“泡沫排序法(Bubble sorting)”於最壞情況(worst case)下，其完成資料排序所需 之時間複雜度為何？
(A) O(n)
(B) O(2n)
(C) O(2n )
(D) O(n 2 )

答案：登入後查看
統計： A(1), B(8), C(3), D(17), E(0) #3228041

詳解 (共 1 筆)

#6209880

泡沫排序法的最壞情況發生在資料完全逆序時。其排序過程需要進行多次比較和交換，並且每次遍歷都需要比較相鄰的元素。具體來說：

  • 在第一次遍歷中，泡沫排序會比較並交換 n−1次。
  • 在第二次遍歷中，會比較並交換 n−2 次。
  • 如此類推，直到最後一次遍歷比較一次。

因此，總的比較次數是 (n−1)+(n−2) +1，這是一個等差數列的和，為n(n-1)這在大O符號中簡化為 O(n^2)。

0
0