作者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