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)}不是不為相依嗎？

中央第一題答案是什麼?

空間複雜度要看變動的部分，這題是遞迴的stack部分，每次遞迴會傳2/3的資料量進去，return後又跑下一個遞迴，所以需要的空間是一個2/3資料量的子問題空間https://i.imgur.com/beniLNJ.jpghttps://imgur.com/beniLNJ.jpg2我也會選B欸不知道還有哪裡沒想到QQ3應該是小的LD大的必LD，大的LI小的必LI才對吧(?

數學那題應該是給錯答案

第一題應該是解T(n)=3T(2/3n)，我算e，有錯請指正！懂了 謝謝s大和a大！為什麼不是需要3*2/3的子空間呢？

他不是三個同時call的，一次call完一個遞迴，return後才會call第二個所以準備一份空間就夠了，第一個用完給第二個用

我懂了，謝謝！

(1,0)(0,1)(1,1)(2,2)拿掉(1,0)還是相依 應該沒錯吧更正一下他是說子集是相依 那原本會相依吧?

是 子集相依原本就會相依

我翻書是false 原po是對的 我太急了

所以數學那題 C要選還不選？他不是說小的相依 大的也會相依嗎？

題目是說大的相依，則小的也會相依

應該是abe

看錯了 了解～

不好意思問一下第一題 傳array不是pass by reference嗎為何為需要額外的空間? 我覺得是O(1)欸

但是指標還是得宣告一個空間來放array的值吧？

是exchange要O(1) 總共有遞迴O(logn)次嗎筆記是寫tree的高度當space complexity好像都是寫遞迴人呼叫的額外[email protected]@

瞭解了 我好像誤會前面S大的意思了 感謝樓上大大解釋