[請益] Bubble Sort時間複雜度

[vito9580 (vito)]

各位前輩好，最近在研讀演算法及時間複雜度部分，由於時間複雜圖計算還是不是很確
定，想請版上各位可以幫忙一起確認
如圖為改良板的bubble sort，想請問他的時間複雜度是否為O(N) ？？

程式：

https://i.imgur.com/bq5wPvO.jpg

結果：
https://i.imgur.com/2iUaKIB.jpg

感謝


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.204.168.181
※ 文章網址: https://www.ptt.cc/bbs/Programming/M.1556951174.A.B59.html
→ LPH66: 你沒分析到 while(!flag) 的次數
→ LPH66: 給一個反向排列的陣列就會看到外圈也 N 次
→ LPH66: 所以還是 O(N^2)
→ alan7788: 沒記錯的話現在sort的下限是O(nlog(n))
→ alan7788: ，如果真的到O(n)的話可以發論文了吧
→ eddie55020: 只有比較排序才有O(nlogn)的限制，像
→ eddie55020: 是Counting sort就可以小於O(nlogn)
推 alan23273850: 比較排序下界是nlog(n)已經是被證明
→ alan23273850: 的結果，課本上都有，不難
→ alan23273850: counting sort可以線性沒錯，可是數
→ alan23273850: 值範圍有限制
推 brianhsu: 可以把過程印出來，和加個 counter，會
→ brianhsu: 比較有感覺為什麼是 n^2，我都是這樣。