首页 试题详情
单选题

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

AO(n)

BO(nlgn)

CO(n2)

DO(n2lgn)

正确答案

答案解析 

对于递归式，假设T(1)=1，则：
T(n)=T(n-1)+n
=T(n-2)+n-1+n
=T(n-3)+n-2+n-1+n
=1+2+…+n-1+n
=n(n+1)/2
可见，时间复杂度为O(n2)。若问题的规模增加了16倍，则运行时间增加了162=256倍。

相似试题

  • 单选题

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

    答案解析

  • 单选题

    算法的时间复杂度取决于()。

    答案解析

  • 单选题

    算法的时间复杂度是指______。

    答案解析

  • 单选题

    TN-S俗称( )。

    答案解析

热门题库