1.
離散課本上冊5-58 範例7
不太懂為何他解時間複雜度f(n) = O(n)
是令g(n) = f(n) - f(n-1)
2.
離散課本上冊5-71 範例5
最後的答案為何會獨立出一個 r = 0的解
為何不是
ar = -(-1) ^r + (1/2)(-2)^r, if r>=0
3.
離散課本上冊5-83 範例7(a)
不太懂他在幹嘛....
前面幾項了解...但最後一項 根號{ (n-1)^2 + [(n^2 -1 ) - (n-1)^2] }
是怎麼來的.....
麻煩各位解惑 謝謝
1 則留言:
1. 因為f(n)的遞迴式有floor及ceiling, 無法直接解遞迴, 利用g(n) = f(n)-f(n-1)才有辦法變成一個可解的遞迴, 這題的技巧比較高
2. 因為A(x)前面有個1/2, 那一項只會貢獻到x^0的係數, 所以要把r = 0的結果加上1/2, 其他r >= 1時不會加那個1/2
3. 你可以試著把n代一些值進去看看, 或許會更清楚一些, 因為那個和項只到n^2 - 1, 當取根號時, 它的值都會是n - 1, 目的是要算總共有幾項, 例如n = 3, k的範圍由2^2到3^2 - 1, 即4, 5, 6, 7, 8, 這些數取根號再floor, 這些值都是2, 總共有5項, 最後的那一項根號裡頭的值其實只是n^2 - 1而已, 寫成那樣只是要確定項數
張貼留言