[理工] 資結 排序可以達到多快的問題

[AAQ8 ()]

https://i.imgur.com/4kc0tZv.jpg

這筆記是講排序可以達到多快

筆記有提到要用log(n!) 不能用nlogn

是因為nlogn是成長速率

沒辦法看出真正比較次數嗎

不知道我這樣理解有沒有錯誤


順便問個小疑惑

洪逸上課時會上DS版的和ALGO版的

像是Quick sort就有兩個版本

那考試時是要寫哪個版本

要依題目要求 還是考DS就寫DS版的 ALGO就寫ALGO版的

謝謝


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.28.102.192
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1528358495.A.652.html
推 TWkobe: 原本是用decision 證明 你查一下就知道了
→ TWkobe: 基本上資結與algo的quick差不了多少
→ TWkobe: 主要有選pivot差異 iterative,recusive做法
→ TWkobe: 補字 decision tree
推 alan23273850: 我覺得那個 example 的註明應該是想強調真正次數跟
→ alan23273850: 時間複雜度差常數倍吧
→ alan23273850: 本來就不能拿漸進式的結果當作實際執行次數
我懂了 謝謝
※ 編輯: AAQ8 (219.70.197.208), 06/08/2018 00:42:02