Question

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

Answer 1

　　 设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的时候 需要对较小的Fn Fn … Fl F 精确计算多少次?

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

　　【清华大学 二( 分)】

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

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

　　【中科院计算所 】

lishixinzhi/Article/program/sjjg/201311/22837