问题 单项选择题

下面函数中渐进时间最小的是()。

A.T1(n)=n+nlogn

B.T2(n)=2n+nlogn

C.T3(n)=n2-logn

D.T3(n)=n+100logn

答案

参考答案:D

解析:

[分析] 渐进时间是考虑当问题规模n趋于无穷时函数随时间变化的趋势。所以在比较两个函数的渐进时间时应考虑最高数量级,若相同则必须进一步考虑渐进表达式中的常数因子,以此类推。当n无限增大时,T4<T1<T2,T4<T3,所以T4的渐进时间最小。

问答题
多项选择题