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

看板Grad-ProbAsk作者 (Shanboy)時間8年前 (2017/02/06 16:01), 8年前編輯推噓3(3推 0噓 6→)
留言9則, 5人參與, 最新討論串5/5 (看更多)
借標題問個～ 請問一下第一大題的(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
→
02/06 16:03, , 1F
我答案也寫B
02/06 16:03, 1F
→
02/06 16:03, , 2F
因為他給的i是index，還是要花O(n)的時間先找到該node
02/06 16:03, 2F
推
02/06 16:04, , 3F
洪逸筆記有說原因 我覺得比較有問題的是D
02/06 16:04, 3F
→
02/06 16:07, , 4F
l大可以詳細說明一下嗎@@?
02/06 16:07, 4F
推
02/06 16:12, , 5F
如果A是對的話 那single跟double的時間複雜度應該同等級才
02/06 16:12, 5F
→
02/06 16:12, , 6F
對@@
02/06 16:12, 6F
→
02/06 16:12, , 7F
A的話洪逸筆記是假設前一個點都是已知的@@
02/06 16:12, 7F
推
02/06 16:14, , 8F
我會寫O(n),因為他function的引數沒有給該點指標
02/06 16:14, 8F
→
02/06 16:15, , 9F
我看到的洪逸的說法是跟原PO一樣，是要給兩個指標
02/06 16:15, 9F
‣ 更多 Kingsword 的文章
文章代碼(AID): #1Oc2rj8d (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 5 之 5 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共5篇)
‣ 更多 Kingsword 的文章
文章代碼(AID): #1Oc2rj8d (Grad-ProbAsk)