これは、最適化されたバブル ソート アルゴリズムの擬似コードです。その時間の複雑さを分析しようとしましたが、4 行目のコストがいくらかわかりません (A[i-1] > A[i] の場合)。答えは (n-1)+(n-2)+........+1 ですか? また、5 行目から 8 行目までの費用はいくらですか?
1.for j = A.length to 2
2. swapped = false
3. for i = 2 to j
4. if A[i-1] > A[i]
5. temp = A[i]
6. A[i-1] = A[i]
7. A[i-1] = temp
8. swapped = true
9. if(!swapped)
10. break