某算法的时间复杂度表达式为T(n)=an2+bnlgn+cn+d,其中,n为问题

最全题库2022-08-02  33

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

选项 A.O(n2)
B.O(n)
C.O(nlgn)
D.O(1)

答案 A

解析 本题考查算法分析的基础知识。
在算法分析中,符号O用于表示算法运行时间的上限。从定义上说,对一个函g(n),O(g(n))表示函数集合:
{f(n):存在正常数c和n0,使得对所有的n≥n0,有0≤f(n)≤cg(n)}
根据上述定义,可以知道表达式T(n)=an2+bnlgn+cn+d在函数集合O(n2)中。对此问题,简单的做法是忽略n的低阶项和最高阶项n2的常系数,故答案应为O(n2)。
转载请注明原文地址:https://tihaiku.com/congyezige/2410086.html

最新回复(0)