[理工] 兩題資結

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