2. 从业资格
  3. 某算法的时间复杂度可用递归式表示，若用表示该算法的渐进时间复杂度的紧致界，则正确

某算法的时间复杂度可用递归式表示，若用表示该算法的渐进时间复杂度的紧致界，则正确

题库2022-08-02  36
问题 某算法的时间复杂度可用递归式表示，若用表示该算法的渐进时间复杂度的紧致界，则正确的是（　　）。
选项
答案 A
解析 在本题中，我们关键要理解算法的渐进紧致界的概念，举个例子来说吧，假设当N>N0时，函数f（N）在一个常数因子范围内等于g（N），则称g（n）是f（n）的一个渐近紧致界。
【《软件设计师教程（第5版）》--P422页】
根据主定理（定理8.1），此递归式中，a=2，b=2，logba=1，则f（n）=nlgn=nlogbalgkn=nlogbalgn，属于规则（2），（其中k=1），因此，T（n）=O（nlogbalgk+1n）=O（nlg2n）。本题选择A选项。
本题中给出的递归式的渐进紧致界应该是A。
转载请注明原文地址:https://tihaiku.com/congyezige/2409918.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

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