[理工] 107中央 資結 線代

看板Grad-ProbAsk作者 (開心就拍手)時間7年前 (2019/01/05 01:54), 7年前編輯推噓8(8推 0噓 24→)
留言32則, 9人參與, 7年前最新討論串1/1
https://i.imgur.com/AHrzUme.jpg
請問第2題的space要怎麼算？ 每次除以3所以是logn嗎？ https://i.imgur.com/GdorYDE.jpg
第3題我寫b但有看到別人答案寫c https://i.imgur.com/GF1oTqe.jpg
c選項 如果S={(1, 0), (0, 1), (1, 1)}為相依 但子集{(1, 0), (0,1)}不是不為相依嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.9.166.91 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1546624494.A.4C2.html ※ 編輯: yulintsai (39.9.166.91), 01/05/2019 01:55:29
推
01/05 09:28, 7年前 , 1F
中央第一題答案是什麼?
01/05 09:28, 1F
推
01/05 12:14, 7年前 , 2F
空間複雜度要看變動的部分，這題是遞迴的stack部分，每
01/05 12:14, 2F
→
01/05 12:14, 7年前 , 3F
次遞迴會傳2/3的資料量進去，return後又跑下一個遞迴，
01/05 12:14, 3F
→
01/05 12:14, 7年前 , 4F
所以需要的空間是一個2/3資料量的子問題空間https://i.im
01/05 12:14, 4F
→
01/05 12:14, 7年前 , 5F
gur.com/beniLNJ.jpg
01/05 12:14, 5F
推
01/05 12:16, 7年前 , 6F
01/05 12:16, 6F
→
01/05 12:16, 7年前 , 7F
2我也會選B欸不知道還有哪裡沒想到QQ
01/05 12:16, 7F
→
01/05 12:16, 7年前 , 8F
3應該是小的LD大的必LD，大的LI小的必LI才對吧(?
01/05 12:16, 8F
→
01/05 12:20, 7年前 , 9F
數學那題應該是給錯答案
01/05 12:20, 9F
→
01/05 13:27, 7年前 , 10F
第一題應該是解T(n)=3T(2/3n)，我算e，有錯請指正！
01/05 13:27, 10F
→
01/05 13:28, 7年前 , 11F
懂了 謝謝s大和a大！
01/05 13:28, 11F
→
01/05 13:40, 7年前 , 12F
為什麼不是需要3*2/3的子空間呢？
01/05 13:40, 12F
推
01/05 13:51, 7年前 , 13F
他不是三個同時call的，一次call完一個遞迴，return後才
01/05 13:51, 13F
→
01/05 13:51, 7年前 , 14F
會call第二個
01/05 13:51, 14F
→
01/05 13:53, 7年前 , 15F
所以準備一份空間就夠了，第一個用完給第二個用
01/05 13:53, 15F
→
01/05 13:54, 7年前 , 16F
我懂了，謝謝！
01/05 13:54, 16F
推
01/05 16:39, 7年前 , 17F
(1,0)(0,1)(1,1)(2,2)拿掉(1,0)還是相依 應該沒錯吧
01/05 16:39, 17F
推
01/05 16:42, 7年前 , 18F
更正一下他是說子集是相依 那原本會相依吧?
01/05 16:42, 18F
推
01/05 17:02, 7年前 , 19F
是 子集相依原本就會相依
01/05 17:02, 19F
推
01/05 17:18, 7年前 , 20F
我翻書是false 原po是對的 我太急了
01/05 17:18, 20F
→
01/06 01:23, 7年前 , 21F
所以數學那題 C要選還不選？
01/06 01:23, 21F
→
01/06 01:23, 7年前 , 22F
他不是說小的相依 大的也會相依嗎？
01/06 01:23, 22F
→
01/06 01:24, 7年前 , 23F
題目是說大的相依，則小的也會相依
01/06 01:24, 23F
→
01/06 01:40, 7年前 , 24F
應該是abe
01/06 01:40, 24F
→
01/06 02:06, 7年前 , 25F
看錯了 了解～
01/06 02:06, 25F
→
01/06 02:52, 7年前 , 26F
不好意思問一下第一題 傳array不是pass by reference嗎
01/06 02:52, 26F
→
01/06 02:53, 7年前 , 27F
為何為需要額外的空間? 我覺得是O(1)欸
01/06 02:53, 27F
→
01/06 04:30, 7年前 , 28F
但是指標還是得宣告一個空間來放array的值吧？
01/06 04:30, 28F
→
01/06 06:42, 7年前 , 29F
是exchange要O(1) 總共有遞迴O(logn)次嗎
01/06 06:42, 29F
→
01/06 06:43, 7年前 , 30F
筆記是寫tree的高度當space complexity
01/06 06:43, 30F
→
01/06 06:53, 7年前 , 31F
好像都是寫遞迴人呼叫的額外stack@@
01/06 06:53, 31F
→
01/06 12:14, 7年前 , 32F
瞭解了 我好像誤會前面S大的意思了 感謝樓上大大解釋
01/06 12:14, 32F
‣ 更多 yulintsai 的文章
文章代碼(AID): #1SBvtkJ2 (Grad-ProbAsk)