列表

详情


某算法的时间复杂度表达式为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用于表示算法运行时间的上限。从定义上说,对一个函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)。

上一题