Re: [其他] 離散：遞迴以及時間複雜度

[LPH66 ( )]

※ 引述《pmove (不怕死，才算真正的活著)》之銘言：
: g(k) = { g(k/2) if k is even,
:          g(Floor(k/2)+1) + Floor(k/2) if k is odd,
:        }
: with g(1) = -1
: Note: Floor表示向下取整
: 1. 請問計算這個遞迴的時間複雜度是Big O(logk)? 還是Big O(1)?
: 2. 請問上面這個g(k)是不是有辦法解遞迴成一個式子？
: 3. 如果有辦法解遞迴成式子，那時間複雜度是不是Big O(1)?
: 我問這個，主要是有點迷惑，是不是解遞迴後，
: 時間複雜度，有可能降低？還是時間複雜度一定維持不變？
你要注意你的遞迴是在描述什麼東西

如果這遞迴是直接描述你想要計算的值的話, 當然求出通式出來就是 O(1)

但如果你這遞迴是在描述一個遞迴演算法的操作次數的話

你解出來的只是原演算法的時間複雜度, 對原演算法的加速沒有幫助

你應該是把這兩個概念給混在一起了才會迷惑說到底解遞迴能不能加速

因為兩者都是遞迴, 但描述的東西不一樣

舉個例子:

H(n) = 2 * H(n/2) + n, H(1) = 0

如果你只是想算 H(n) 的值多少那你可以解得 H(n) = n*log2(n)

那代隨便一個 n 值去算函數值當然是 O(1)

但如果 H(n) 是在描述合併排序演算法的操作數目的話

解出來的 H(n) 式子對合併排序演算法加速是沒有用的

因為這就代表合併排序演算法的時間複雜度就是 O(n*log(n))

--
 ◢ ˊ_▂▃▄▂_ˋ. ◣　　　　　 　　　　▅▅　▅▅　ι●╮　　 █▄▄▄▄▄   
▍./◤_▂▃▄▂_◥ \'▊ 　　ＨＡＲＵＨＩ █████　＜■┘  　 ▄▄▄▄▄▄▄ 
▎⊿ ◤◤◥█◥◥█Δ   　　ＩＳＭ　 　　By-gamejye　￠|\  　　▌▌▌▌▌▄▌▌
▏ζ(▏●‵◥′●▊)Ψ ▏　　 　　　 　　　　█　　　 ⊿Δ 　　▄▄▄  ▄▄▄▄
█/|▊ 〃  、  〃▋ |\ ▎　　　　　 　 　ハルヒ主義　　　  　　█▄▄▄█▄▄  
◥◥|◣   ‵′  ◢/'◢◢S.O.S 世界を大いに盛り上げるための涼宮ハルヒの団　　　 

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.177.0.237 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1630075491.A.3F7.html
※ 編輯: LPH66 (180.177.0.237 臺灣), 08/27/2021 22:45:19
推 pmove       : 遞迴是直接描述所要計算的值
→ mantour     : 求出通式不代表值會自己變出來, 是否還要考慮用什
→ mantour     : 麼演算法去求通式的值
→ mantour     : 比如求費式數列第n項, 單純遞迴是 O(n^2)
→ mantour     : 解出通式變成 c(a^n - b^n)
→ mantour     : 而求a^n如果用最笨的演算法是 O(n) , 如果聰明一點
→ mantour     : 則是 O(log n)
→ mantour     : 更正 單純遞迴是 O(2^n)
→ mantour     : 即使不解出通式, 本來的遞迴式如果改用動態規劃建表
→ mantour     : 也可以變成O(n), 其實解出通式也是演算法的一種
→ mantour     : 用不同演算法去算遞迴的值, 複雜度可以不同應該很
→ mantour     : 合理吧
推 Vulpix      : 費氏數列用定義遞迴是O(n)吧，每多算一項也只要一次
→ Vulpix      : 加法。就算連call前兩項都要算進去，也還是O(n)。
推 arrenwu     : 費氏數列用單純遞迴 f(n) = f(n-1)+f(n-2)是O(2^n)
→ arrenwu     : O(n) 是用for-loop(迭代)或者加入memoization
→ LPH66       : 直接寫不管重覆的應該是 O(φ^n) = O(f(n))
→ LPH66       : (因為唯一的終止條件是 f(1)=f(2)=1)
→ LPH66       : 用 memoization 或 DP 式才是 O(n) 沒錯
→ LPH66       : 然後計算通式的話指數可以用對數做, 這就成了 O(1)
→ LPH66       : 啊, 我是在說任意底指數要乘一個對數值...
→ LPH66       : 自然指數和自然對數即使用級數, 算到固定精度的時間
→ LPH66       : 可以當做 O(1), 所以算通式在這意義下是 O(1)
推 Vulpix      : memorization是指這種嗎？f(n)=f(n-1)+g(n-1)然後配
→ Vulpix      : 上g(n)=f(n-1)←這個？
→ Vulpix      : 還真的沒有r，好不直覺……
→ LPH66       : memoization 是算過的值寫下來, 之後要就直接拿
推 Vulpix      : 所以如果之後要多次讀取的話會很方便，但要付出記憶
→ Vulpix      : 體空間給他的概念吧。那跟上面那個是還有點不一樣，
→ Vulpix      : 那個寫法是過氣的f,g可以扔掉。