作者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/cn.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