Re: [理工] 104 台大資工 線代 OS DS 對答案

[Kingsword (Shanboy)]

借標題問個～

請問一下第一大題的(6)

第一個表格所提及的linked list應該是用singly linked list？

那Delete的操作因為只給要刪除的node之pointer沒給前一個pointer

所以必須花O(n)的時間尋找

這樣答案應該B不是嗎？ 為何是O(1)呢？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.176.32.167
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486368109.A.227.html
※ 編輯: Kingsword (180.176.32.167), 02/06/2017 16:02:20
→ yupog2003: 我答案也寫B
→ yupog2003: 因為他給的i是index，還是要花O(n)的時間先找到該node
推 leoone: 洪逸筆記有說原因 我覺得比較有問題的是D
→ Kingsword: l大可以詳細說明一下嗎@@?
推 leoone: 如果A是對的話 那single跟double的時間複雜度應該同等級才
→ leoone: 對@@
→ leoone: A的話洪逸筆記是假設前一個點都是已知的@@
推 krusnoopy: 我會寫O(n),因為他function的引數沒有給該點指標
→ gouya: 我看到的洪逸的說法是跟原PO一樣，是要給兩個指標