[問卦] Big O為什麼有平均情況?消失

看板Gossiping作者時間6年前 (2018/05/12 22:02), 編輯推噓3(7推 4噓 7→)
留言18則, 16人參與, 最新討論串1/1
安安 Big O建立的不是最壞情況執行時間嗎? 為什麼會有平均情況呢? 像是quick sort的worst case是O(n^2) 但平均情況是O(n*logn) 雖然可以理解平均情況的n*logn怎麼來的 Why??? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 219.68.110.58 ※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1526133734.A.75D.html
→
05/12 22:02, , 1F
你一定沒有看過BIG O的詳細定義
05/12 22:02, 1F
推
05/12 22:03, , 2F
現在47負我們文組看不懂484 森77
05/12 22:03, 2F
推
05/12 22:03, , 3F
Oscar Robertson
05/12 22:03, 3F
→
05/12 22:03, , 4F
我問過然後被罵了
05/12 22:03, 4F
→
05/12 22:04, , 5F
05/12 22:04, 5F
→
05/12 22:04, , 6F
還有big theta big omega
05/12 22:04, 6F
推
05/12 22:06, , 7F
四樓解答
05/12 22:06, 7F
推
05/12 22:07, , 8F
big O不是指worst case 你的前提就是錯惹
05/12 22:07, 8F
推
05/12 22:10, , 9F
注意 big O 指的是漸進線上界，跟什麼 case 無關
05/12 22:10, 9F
噓
05/12 22:15, , 10F
你連甚麼是quick sort都不知道吧
05/12 22:15, 10F
推
05/12 22:16, , 11F
我文組看不懂啦
05/12 22:16, 11F
噓
05/12 22:34, , 12F
O(n)
05/12 22:34, 12F
→
05/12 22:43, , 13F
再回去看看定義吧
05/12 22:43, 13F
噓
05/12 22:43, , 14F
選2^n 就對了
05/12 22:43, 14F
→
05/12 23:05, , 15F
數據間的關聯性 統計的結果
05/12 23:05, 15F
推
05/12 23:05, , 16F
駕駛員是羅傑
05/12 23:05, 16F
→
05/12 23:19, , 17F
Show Time~~~~~ (BGM響起
05/12 23:19, 17F
噓
05/12 23:47, , 18F
拆巢狀遞迴就對了
05/12 23:47, 18F
‣ 更多 tmacfly 的文章
文章代碼(AID): #1QzlFcTT (Gossiping)