2. 计算机
  3. 某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为_______，若问题的规模增加了16倍，则运行时间增加 _______倍。 (63)

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

admin2019-07-12  57
问题 某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为_______，若问题的规模增加了16倍，则运行时间增加 _______倍。
(63)
选项 A、16
B、64
C、256
D、1024
答案C
解析 对于递归式，假设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倍。
转载请注明原文地址:https://kaotiyun.com/show/G9CZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)