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

题库2022-08-02  39

问题 某算法的时间复杂度可用递归式表示,若用表示该算法的渐进时间复杂度的紧致界,则正确的是(  )。

选项

答案 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)