數據結構考研分類復習真題 第一章 答案[9]

　　（）由斐波那契數列的定義可得

　　Fn=Fn+Fn
　　=Fn+Fn
　　=Fn+Fn
　　=Fn+Fn
　　=Fn+Fn
　　……
　　=pF+qF

　　設Fm的執行次數為Bm(m=…n)由以上等式可知Fn被執行一次即Bn=Fn被執行兩次即Bn=直至F被執行p次F被執行q次即B=pB=qBm的執行次數為前兩等式第一因式系數之和即Bm=Bm+Bm再有Bn=和Bn=這也是一個斐波那契數列可以解得

　　      (m=…n)

　　（）時間復雜度為O(n)

　　．從小到大排列為logn n/+logn n nlogn n+lognn  nn+n n/ (/)n n!

[]  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23260.html