02331数据结构
在分析各种算法的时间复杂度时，一般只讨论相应的数量级，用f（n）表示，请问其中n的含义是（）。
题目
在分析各种算法的时间复杂度时，一般只讨论相应的数量级，用f（n）表示，请问其中n的含义是（）。
参考答案和解析
相似问题和答案
第1题：
A对于任何的数据量，A算法的时间开销都比B算法小
B随着问题规模n的增大，A算法比B算法有效
C随着问题规模n的增大，B算法比A算法有效
D对于任何数据量，B算法的时间开销都比A算法小
第2题：
A.O(n)
B.O(n²)
C.O(e)
D.O(eloge)
F.O(e²)
第3题：
此题为判断题(对，错)。
第4题：
算法复杂度包括时间复杂度和空间复杂度。对于时间复杂度，一般可以用平均性态和最坏情况复杂性来衡量：对于空间复杂度，一般指执行该算法所需要的【 】。
内存空间
第5题：
若n表示问题的规模、O(f(n))表示算法的时间复杂度随n变化的增长趋势，则算法时间复杂度最小的是(59)。
A．O(n2)
B．O(n)
C．O(logn)
D．O(nlogn)
解析：本题考查的是算法消耗的时间度量。一般情况下，一个算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))，它表示随问题n的增大，算法执行时间的增长率和 f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。显然，在O(n2)、O(n)、 O(logn)和O(nlogn)中，复杂度最小的是O(logn)。
第6题：
A、时间复杂度
B、空间复杂度
C、执行的时间
D、占用的空间
第7题：
若一个算法的时间复杂度为(n2+2n-3)/(2n)，其数量级表示为______。
O(n) 解析：算法的时间复杂度表示是根据问题规模的函数f(n)来衡量的，其中问题规模函数的表达式(n2+2n-3)/(2n)中，问题规模增长或减少的比与n一致。
第8题：
某算法的时间复杂度可用递归式[*],表示，若用[*]表示该算法的渐进时间复杂度的紧致界，则正确的是(62)。
A．
(nlg2n)
B．(nlgn)
C．(n2)
D．(n3)
解析：本题利用递归树方法求解。得到的递归树如下图所示：
由于C属于O(nlg2n)且C属于Ω(nlg2n)，所以总的时间复杂度为A。
第9题：
计算N!的递归算法如下，求解该算法的时间复杂度时，只考虑相乘操作，则算法的计算时间T(n)的递推关系式为(55)；对应时间复杂度为(56)。
int Factorial (int n)
{//计算n!
if(n＜=1)return 1;
else return n * Factorial(n-1);
}
(62)
A．T(n)=T(n-1)+1
B．T(n)=T(n-1)
C．T(n)=2T(n-1)+1
D．T(n)=2T(n-1)-1
第10题：
给定一个由n个数组成的序列，要求该序列的最长单调上升子序列，请设计对应的算法并分析其时间复杂度，如果时间复杂度劣于O（nlogn）的，将其优化为O（nlogn）时间复杂度的算法。
正确答案: 假设当前已求出m[1..i-1]，当前保留的状态集合为S，下面计算m[i]。
1、若存在状态k∈S，使得x[k]=x[i]，则状态m[i]必定不需保留，不必计算。因为，不妨设m[i]=m[j]+1，则x[j]
从性质D和算法描述可以发现，S实际上是以x值为关键字（也是以m值为关键字）的有序集合。若使用平衡树实现有序集合S，则该算法的时间复杂度为O（n*logn）。（每个状态转移的状态数仅为O（1），而每次状态转移的时间变为O（logn））。