2. 从业资格
  3. 在某个算法时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算

在某个算法时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算

考试题库2022-08-02  49
问题 在某个算法时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为（　　），若问题的规模增加了16倍，则运行时间增加（　　）倍。问题1选项A.Θ(n)B.Θ(nlgn)C.Θ(n2)D.Θ(n2lgn)问题2选项A.16B.64C.256D.1024
选项
答案 CC
解析 由于递归式为：T（n）=T（n-1）+n。我们可以把一个规模为n的时间复杂度算出来。
分析过程为：
T（n）=T（n-1）+n；
T（n-1）=T（n-2）+n-1；
T（n-2）=T（n-3）+n-2；
....
T（n）=1+2+..+n-1+n。
这是一个典型的等差数列。用数列求和公式有：（（1+n）*n）/2。这样就求得时间复杂度为：Θ（n2）。
后面一问则有：
当问题规模为n时，时间复杂度Θ（n2）。
当x=16n时，时间复杂度Θ（x2）=Θ（（16n）2）=Θ（256n2）。
转载请注明原文地址:https://tihaiku.com/congyezige/2409627.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

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