這是讀sum of subset解答出現神奇的式子..請問為什麼
二、請問這個演算法的operation低到(3n/2)-2嗎? (怎麼看都很像樹Orz)
三、True or false
The language L={xx| x is a string of 0s and 1s} is a finite state language.
謝謝助教&you
訂閱：
張貼留言 (Atom)
Research Space for Linear Algebra & Discrete Mathematics
2 則留言:
1. 你給的資訊有點少, 要看 k 是什麼
2. 這個 Procedure 直接寫 T(n)=(3n/2)-2 怪怪的, 因為 n 不一定是 power of 2 (即使是算出來應該也不是這個數字), 我覺得應該也寫不出一個精確的時間, 若只分析它的 complexity, 因為 T(n) = 2T(n/2) + theta(1), 用 Master theorem 即可知 T(n)=O(n); 不過這個演算法的目的應該是要找出minimum和maximum number, 這確實是有一個只要做 T(n) = 3n/2 - 2 次 comparison 的方法, 但不是這個
3. True
第三題稍微改一下, 這題是false, 證明可參考題庫班講義最後一本, 清大資應的題目
張貼留言