数据结构第1章 绪论[7]

设n是偶数试计算运行下列程序段后m的值并给出该程序段的时间复杂度

m:=;

FOR i:= TO n DO

FOR j:=*i TO n DO

m:=m+;

【南京邮电大学 一】

有下列运行时间函数

()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= Fl= Fn=Fn+Fn n=

请就此斐波那契数列回答下列问题

() (分) 在递归计算Fn的时候需要对较小的FnFn… Fl F精确计算多少次?

() (分) 如果用大O表示法试给出递归计算Fn时递归函数的时间复杂度录多少?

【清华大学 二(分)】

将下列函数按它们在n→∝时的无穷大阶数从小到大排序

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

【中科院计算所 】

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