申論題

C語言函數實現的氣泡排序（Bubble Sort）演算法的時間複雜度為O(n²)。這是因為它包含兩個嵌套循環，其中外部循環運行n-1次，內部循環最多運行n次。在最壞的情況下（即數組是逆序的），每個元素都需要與其後面的每個元素比較並可能交換，因此需要執行n(n-1)/2次比較和交換操作。

void ourBubbleSort (int *iArray, int n) // 1 {for (i=0; iiArray[j]) // (n^2-n)*(n-1)/2 { int iTemp =iArray[i]; iArray[i] = iArray[j]; iArray[j] = iTemp; } }

總次數為 1 + n-1 + (n^2-n)*(n-1) => n^3 -2n^2 時間複雜度為 O(n^3)