作者AAQ8 ()
看板Grad-ProbAsk
標題[理工] 兩題資結
時間Wed Nov 21 20:54:41 2018
https://i.imgur.com/wGylg0Y.jpg
https://i.imgur.com/PS0ZeWZ.jpg
第一張的算式看得懂
不過不知道為什麼是那樣子算
第二張的b選項不知道錯在哪裡
麻煩各位
感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.28.34.21
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1542804884.A.9C5.html
1F：推 skyHuan: 你沒拍到上一題XD 11/21 21:05
2F：→ skyHuan: 我記得這題好像跑了三個遞迴，資料量都是原本的2/3，空 11/21 21:05
3F：→ skyHuan: 間複雜度主要算的就是變動空間，這題就是跑遞迴的時候的s 11/21 21:05
4F：→ skyHuan: tack，他三次是分開跑的，每次需要的空間就是原本的2/3， 11/21 21:05
5F：→ skyHuan: 所以s(n)=s(2n/3)+O(1) 11/21 21:05
6F：→ skyHuan: (B) 的話不一定，事實上把空間變成2^n很可能光access這 11/21 21:06
7F：→ skyHuan: 些空間，時間複雜度就2^n了 11/21 21:06
8F：→ AAQ8: 想請問一下，時間複雜度是執行次數的成長速度，空間複雜度是 11/22 14:11
9F：→ AAQ8: 指記憶體需求的成長速度，這樣子說正確嗎 11/22 14:11
10F：推 skyHuan: 是的~ 就是當資料量是n的時候這個演算法需要多少時間/空 11/23 00:01
11F：→ skyHuan: 間隨n改變的程度 11/23 00:01