作者yulintsai (開心就拍手)
看板Grad-ProbAsk
標題[理工] 107中央 資結 線代
時間Sat Jan 5 01:54:52 2019
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1546624494.A.4C2.html
※ 編輯: yulintsai (39.9.166.91), 01/05/2019 01:55:29
1F：推 daiyani5566: 中央第一題答案是什麼? 01/05 09:28
2F：推 skyHuan: 空間複雜度要看變動的部分，這題是遞迴的stack部分，每 01/05 12:14
3F：→ skyHuan: 次遞迴會傳2/3的資料量進去，return後又跑下一個遞迴， 01/05 12:14
4F：→ skyHuan: 所以需要的空間是一個2/3資料量的子問題空間https://i.im 01/05 12:14
5F：→ skyHuan: gur.com/beniLNJ.jpg 01/05 12:14
7F：→ skyHuan: 2我也會選B欸不知道還有哪裡沒想到QQ 01/05 12:16
8F：→ skyHuan: 3應該是小的LD大的必LD，大的LI小的必LI才對吧(? 01/05 12:16
9F：→ alen0303: 數學那題應該是給錯答案 01/05 12:20
10F：→ yulintsai: 第一題應該是解T(n)=3T(2/3n)，我算e，有錯請指正！ 01/05 13:27
11F：→ yulintsai: 懂了 謝謝s大和a大！ 01/05 13:28
12F：→ yulintsai: 為什麼不是需要3*2/3的子空間呢？ 01/05 13:40
13F：推 skyHuan: 他不是三個同時call的，一次call完一個遞迴，return後才 01/05 13:51
14F：→ skyHuan: 會call第二個 01/05 13:51
15F：→ skyHuan: 所以準備一份空間就夠了，第一個用完給第二個用 01/05 13:53
16F：→ yulintsai: 我懂了，謝謝！ 01/05 13:54
17F：推 hsu0612: (1,0)(0,1)(1,1)(2,2)拿掉(1,0)還是相依 應該沒錯吧 01/05 16:39
18F：推 hsu0612: 更正一下他是說子集是相依 那原本會相依吧? 01/05 16:42
19F：推 rockieloser: 是 子集相依原本就會相依 01/05 17:02
20F：推 hsu0612: 我翻書是false 原po是對的 我太急了 01/05 17:18
21F：→ o5739201: 所以數學那題 C要選還不選？ 01/06 01:23
22F：→ o5739201: 他不是說小的相依 大的也會相依嗎？ 01/06 01:23
23F：→ Ricestone: 題目是說大的相依，則小的也會相依 01/06 01:24
24F：→ hsu0612: 應該是abe 01/06 01:40
25F：→ o5739201: 看錯了 了解～ 01/06 02:06
26F：→ anonimo: 不好意思問一下第一題 傳array不是pass by reference嗎 01/06 02:52
27F：→ anonimo: 為何為需要額外的空間? 我覺得是O(1)欸 01/06 02:53
28F：→ yulintsai: 但是指標還是得宣告一個空間來放array的值吧？ 01/06 04:30
29F：→ rockieloser: 是exchange要O(1) 總共有遞迴O(logn)次嗎 01/06 06:42
30F：→ rockieloser: 筆記是寫tree的高度當space complexity 01/06 06:43
31F：→ rockieloser: 好像都是寫遞迴人呼叫的額外stack@@ 01/06 06:53
32F：→ anonimo: 瞭解了 我好像誤會前面S大的意思了 感謝樓上大大解釋 01/06 12:14