作者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/cn.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