數據結構考研分類復習真題 第一章 緒論[15]

　　．有下列運行時間函數【吉林工業大學   二（分）】

　　（）T (n)=;    （）T(n)=n+n;     （）T(n)=n+n+n+;

　　分別寫出相應的大O表示的運算時間

　　 試給出下面兩個算法的運算時間【中科院自動化研究所 二 （分）】

　　（）  for  i←   to   n   do
　　x ← x+
　　END

　　（）  for i←    to  n  do
　　for  j←  to  n  do
　　x← x+
　　end
　　end

　　 斐波那契數列Fn定義如下【清華大學 二（分）】

　　F=  F= Fn=Fn+Fn   n=

　　請就此斐波那契數列回答下列問題

　　()  (分) 在遞歸計算Fn的時候需要對較小的FnFn… F F精確計算多少次?

　　()  (分) 如果用大O表示法試給出遞歸計算Fn時遞歸函數的時間復雜度錄多少?

　　．將下列函數按它們在n→∝時的無窮大階數從小到大排序【中科院計算所 】

　　n nn+n nlogn n/ n logn n/+logn (/)nn! n+logn

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

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