[理工] 一題資料結構

看板Grad-ProbAsk作者 (lwhs)時間12年前 (2012/05/01 14:05), 編輯推噓3(3推 0噓 9→)
留言12則, 4人參與, 最新討論串1/1
在某一個系統中需要一個簡單的資料結構，此資料結構僅具有下列三個動作 插入 刪除 和搜尋 。 試分別估計在下列實現方式中最佳的時間複雜度，並解釋其理由 (1) 排序陣列 (sorted array) (2) 未排序陣列 ( unsorted array) 小弟翻資料結構的書 都沒甚麼頭緒 煩請高手解惑 謝謝~ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.223.101.152 ※ 編輯: lwhs 來自: 61.223.101.152 (05/01 14:05)
推
05/01 15:12, , 1F
應該問你排序好的陣列用哪一個方法實現那三個動作最佳
05/01 15:12, 1F
→
05/01 15:13, , 2F
跟未排序好的陣列用哪一個方法去實現那三個動作吧
05/01 15:13, 2F
→
05/01 15:15, , 3F
所以應該排序好的用Insertion未排序的用Merge或Heap吧
05/01 15:15, 3F
→
05/01 15:16, , 4F
明年是考生 如有誤導抱歉了QQ
05/01 15:16, 4F
→
05/01 15:53, , 5F
感謝回答 不過我是在思考該如何下手 ^^
05/01 15:53, 5F
推
05/01 18:24, , 6F
也在練習會遇到的情況 所以我這樣說對嗎XD 需要點回饋
05/01 18:24, 6F
推
05/01 23:22, , 7F
這題的意思應該是 當這個資料結構分別用(1)和(2)去實作時
05/01 23:22, 7F
→
05/01 23:22, , 8F
三種operation的時間複雜度各是多少
05/01 23:22, 8F
→
05/01 23:24, , 9F
若是(1) 則複雜度依序為O(n), O(n), O(log n)
05/01 23:24, 9F
→
05/01 23:24, , 10F
若是(2) 則複雜度依序為 O(1), O(n), O(n)
05/01 23:24, 10F
→
05/02 23:02, , 11F
恩 是在問搜尋的時間複雜度的樣子 謝謝樓上各位的回答^^
05/02 23:02, 11F
→
09/11 15:03, , 12F
這題的意思應該是 當這 https://daxiv.com
09/11 15:03, 12F
‣ 更多 lwhs 的文章
文章代碼(AID): #1FdtqRoY (Grad-ProbAsk)