数据结构考研分类复习真题 第一章 绪论[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

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