作者vito9580 (vito)
看板Programming
標題[請益] Bubble Sort時間複雜度
時間Sat May 4 14:26:12 2019
各位前輩好，最近在研讀演算法及時間複雜度部分，由於時間複雜圖計算還是不是很確
定，想請版上各位可以幫忙一起確認
如圖為改良板的bubble sort，想請問他的時間複雜度是否為O(N) ？？
程式：
https://i.imgur.com/bq5wPvO.jpg
結果：
https://i.imgur.com/2iUaKIB.jpg
感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.204.168.181
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Programming/M.1556951174.A.B59.html
1F：→ LPH66: 你沒分析到 while(!flag) 的次數 123.195.192.32 05/04 17:22
2F：→ LPH66: 給一個反向排列的陣列就會看到外圈也 N 次 123.195.192.32 05/04 17:23
3F：→ LPH66: 所以還是 O(N^2) 123.195.192.32 05/04 17:23
4F：→ alan7788: 沒記錯的話現在sort的下限是O(nlog(n)) 39.10.45.185 05/04 20:14
5F：→ alan7788: ，如果真的到O(n)的話可以發論文了吧 39.10.45.185 05/04 20:14
6F：→ eddie55020: 只有比較排序才有O(nlogn)的限制，像 1.200.59.130 05/04 21:14
7F：→ eddie55020: 是Counting sort就可以小於O(nlogn) 1.200.59.130 05/04 21:14
8F：推 alan23273850: 比較排序下界是nlog(n)已經是被證明 140.112.77.12 05/06 01:50
9F：→ alan23273850: 的結果，課本上都有，不難 140.112.77.12 05/06 01:50
10F：→ alan23273850: counting sort可以線性沒錯，可是數 140.112.77.12 05/06 01:50
11F：→ alan23273850: 值範圍有限制 140.112.77.12 05/06 01:50
12F：推 brianhsu: 可以把過程印出來，和加個 counter，會 223.137.35.61 05/07 08:25
13F：→ brianhsu: 比較有感覺為什麼是 n^2，我都是這樣。 223.137.35.61 05/07 08:25