熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

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

2013-11-15 15:20:14  來源: 數據結構 

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

  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
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.