[理工] [資結]-展開法的觀念問題

看板Grad-ProbAsk作者 (Mu)時間14年前 (2010/02/27 16:09), 編輯推噓2(2推 0噓 0→)
留言2則, 2人參與, 最新討論串1/1
我想請問關於解遞回時間複雜度的問題 有些題目會給類似"T(1)=1"的訊息 但是有些題目並沒有給T(n)帶入的結果 不過詳解過程卻有T帶入某數字的結果 請問這部分是怎麼回事？ ----------- ex: T(n) = 2T(n^1/2) + logn 解答帶入展到最後變成 2^i*T(n^1/2^i) + i*logn, T(2) = 1 然後將i算出來再套回去 ----------- 我想問的是T(2) = 1這個資訊是從何而來的？ 有些題目會給，但沒給的可以推出來嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 163.17.132.161
推
02/27 18:24, , 1F
複雜度一般都是假設T(1) = O(1)
02/27 18:24, 1F
推
02/27 18:53, , 2F
恩 就初值應該是常數 所以不用是T(2)=1 常數即可
02/27 18:53, 2F
‣ 更多 yf2923850 的文章
文章代碼(AID): #1BYDCbzK (Grad-ProbAsk)