PTT數位生活區 / Programming

[請益] Bubble Sort時間複雜度

看板Programming作者 (vito)時間5年前 (2019/05/04 14:26), 編輯推噓2(2推 0噓 11→)
留言13則, 5人參與, 5年前最新討論串1/1
各位前輩好，最近在研讀演算法及時間複雜度部分，由於時間複雜圖計算還是不是很確 定，想請版上各位可以幫忙一起確認 如圖為改良板的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
→
05/04 17:22, 5年前 , 1F
你沒分析到 while(!flag) 的次數
05/04 17:22, 1F
→
05/04 17:23, 5年前 , 2F
給一個反向排列的陣列就會看到外圈也 N 次
05/04 17:23, 2F
→
05/04 17:23, 5年前 , 3F
所以還是 O(N^2)
05/04 17:23, 3F
→
05/04 20:14, 5年前 , 4F
沒記錯的話現在sort的下限是O(nlog(n))
05/04 20:14, 4F
→
05/04 20:14, 5年前 , 5F
，如果真的到O(n)的話可以發論文了吧
05/04 20:14, 5F
→
05/04 21:14, 5年前 , 6F
只有比較排序才有O(nlogn)的限制，像
05/04 21:14, 6F
→
05/04 21:14, 5年前 , 7F
是Counting sort就可以小於O(nlogn)
05/04 21:14, 7F
推
05/06 01:50, 5年前 , 8F
比較排序下界是nlog(n)已經是被證明
05/06 01:50, 8F
→
05/06 01:50, 5年前 , 9F
的結果，課本上都有，不難
05/06 01:50, 9F
→
05/06 01:50, 5年前 , 10F
counting sort可以線性沒錯，可是數
05/06 01:50, 10F
→
05/06 01:50, 5年前 , 11F
值範圍有限制
05/06 01:50, 11F
推
05/07 08:25, 5年前 , 12F
可以把過程印出來，和加個 counter，會
05/07 08:25, 12F
→
05/07 08:25, 5年前 , 13F
比較有感覺為什麼是 n^2，我都是這樣。
05/07 08:25, 13F
‣ 更多 vito9580 的文章
文章代碼(AID): #1SpJ26jP (Programming)
Programming 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 vito9580 的文章
文章代碼(AID): #1SpJ26jP (Programming)