author: cust-- ZKe
---------------------
這里以連乘積加括號問題為背景:
由于矩陣的乘積滿足結合律，且矩陣乘積必須滿足左邊矩陣的列數的等于右邊矩陣的行數，不同的計算順序，需要的乘法運算次數不一樣，加括號可以改變計算順序，合理安排計算順序可以大大降低計算次數，
給乘積算式加括號的方法數是一個計數問題，它的模型是卡特蘭數，
比如有矩陣A,B,C,D，有五種加括號方式
((A*B)*C)*D
(A*(B*C))*D
(A*B)*(C*D)
A*(B*(C*D))
A*((B*C)*D)
可見，無論是哪種加括號的方式，總有一個'*'運算子在最外面的括號的外面，以它作為分隔符，就好像是a*b一樣只有兩個參與運算的乘數，比如A*(B*C*D),而這里的B*C*D同樣是一個有待加括號的乘積算式,這就說明，加括號可以作為一個遞推問題求解，
(不會用博客園編輯latex，再次截圖編輯的latex.....)
這樣，就引入了卡塔蘭數的定義，接下來我們證明該公式，大家只需要掌握《高等數學》的冪級數，柯西乘積，定積分和《離散數學》的牛頓二項式定理，生成函式即可
這樣就證明了該公式，最后我們來求解一下近似公式，畢竟在演算法中我們需要估計函式的階，才能了解演算法的復雜度
這個就更簡單了，大家只需要了解斯特林公式即可，它仍然可以在《離散數學》計數問題里面找到
----------------------------------------------------------
CUST, ZKe
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/65504.html
標籤：其他
上一篇：動態規劃 - 矩陣鏈的乘法問題