时间复杂度记为：T（n）=O（f（n））；其中n是（）。A、函数B、问题的规模C、渐近符号D、规模的函数

T(n)=O(f(n))中，函数O()的正确含义为

A.T(n)为f(n)的函数

B.T(n)为n的函数

C.存在足够大的正整数M，使得T(n)≤M×f(n)

D.存在足够大的正整数M，使得M×f(n)≤T(n)

请编写函数fun()，它的功能是求Fibonacci数列中小于t的最大的一个数，结果由函数返回。其中Fibonacci数列F(n)的定义为

F(0)=0，F(1)=1

F(n)=F(n-1)+F(n-2)

例如：t=1000时，函数值为987。

注意：部分源程序给出如下。

请勿改动主函数main和其他函数中的任何内容，仅在函数fun的花括号中填入所编写的若干语句。

试题程序：

include ＜conio.h＞

include ＜math.h＞

include ＜stdio.h＞

int fun(int t)

{

}

main()

{

int n；

clrscr()；

n=1000；

printf("n=%d， f=%d\n"，n， fun(n))；

}

● 某算法的时间复杂度表达式为 T(n)=an2+bnlgn+cn+d，其中，n为问题的规模，a、b、c和d为常数，用O表示其渐近时间复杂度为 （63）。

（63）A. O(n2) B. O (n) C. O (n1gn) D. O (1)

若n表示问题的规模、O(f(n))表示算法的时间复杂度随n变化的增长趋势，则算法时间复杂度最小的是(59)。

A．O(n2)

B．O(n)

C．O(logn)

D．O(nlogn)

A对于任何的数据量，A算法的时间开销都比B算法小

B随着问题规模n的增大，A算法比B算法有效

C随着问题规模n的增大，B算法比A算法有效

D对于任何数据量，B算法的时间开销都比A算法小

编写函数，isValue()，它的功能是求Fibonacci数列中大于t的最小的一个数，结果由函数返回，其中 Fibonacci数列F(n)的定义为：

F(0)=0，F(1)=1

F(n)=F(n-1)+F(n-2)

最后调用函数writeDat()，把结果输出到文件OUTl0.DAT中。

例如：当t=1000时，函数值为1597。

注意：部分源程序已给出。

请勿改动主函数main()和写函数WriteDat()的内容。

include ＜stdio.h＞

int jsValue(int t)

{

}

main ( )

{

int n;

n=1000;

printf("n=%d, f=%d\n", n, jsValue(n));

writeDat ();

}

writeDat ()

{

FILE *in, *out;

int n, s;

ut = fopen ("OUT10.DAT", "w");

s = jsValue(1O00); printf("% d",s);

fprintf(out, "%d\n", s);

fclose (out);

}

某算法的时间复杂度表达式为T(n)=an2+bnlgn+cn+d，其中，n为问题的规模，a、b、c和d为常数，用O表示其渐近时间复杂度为( )。

A．(n2)

B．O(n)

C．O(nlgn)

D．O(1)

在某个算法时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为（ ），若问题的规模增加了16倍，则运行时间增加（ ）倍。

A.Θ(n) B.Θ(nlgn) C.Θ(n2) D.Θ(n2lgn) A.16 B.64 C.256 D.1024