某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算法的渐进时间复杂度为(请作答此空),若问题的规模增加了16倍,则运行时间增加( )倍。A.O(n)B.O(nlgn)C.O(n2)D.O(n2lgn)

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

A.O(n)
B.O(nlgn)
C.O(n2)
D.O(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)=2T(n/2)+n表示,则该算法的时间复杂度为(59)。A.O(1gn)B.O(nlgn)C.O(n)D.O(n2)

某算法的时间复杂度可用递归式[*],表示,若用[*]表示该算法的渐进时间复杂度的紧致界,则正确的是(62)。A.(nlg2n)B.(nlgn)C.(n2)D.(n3)

某算法的时间复杂度表达式为T(n)=an2+bnlgn+cn+d,其中,n为问题的规模,a、b、c和d为常数,用O表示其渐近时间复杂度为( )。A.(n2)B.O(n)C.O(nlgn)D.O(1)

假设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n,T(1)=1表示,则该算法的时间复杂度为()A.O(logn)B.O(n*logn)C.O(n)D.O(n^2)

某算法的时间代价递推关系为T(n)=2T(n/2)+n,T(1)=1,则该算法的时间复杂度为______。A.O(n)B.C.O(n2)D.O(1)

一个算法的语句执行次数为(2n2+2nlog2n+4n-7),则其时间复杂度为()。A.O(n2)B.O(nlog2n)C.O(n)D.O(2n2)

下列程序段的时间复杂度为()。A.O(n)B.O(n-1)C.O(n2)D.O(log2n)

下面算法的时间复杂度为(34)。 int f(unsigned int n){ if(n=0||n==1)return 1; else return n*f(n-1); }A.O(1)B.O(n)C.O(n2)D.O(n!)

若n表示问题的规模、O(f(n))表示算法的时间复杂度随n变化的增长趋势,则算法时间复杂度最小的是(59)。A.O(n2)B.O(n)C.O(logn)D.O(nlogn)

(接上一题)则时间和空间复杂度分别为(63)。A.O(n2)和O(n)B.O(nlgn)和O(n)C.O(n2)和O(1)D.O(nlgn)和O(1)

对n个基本有序的整数进行排序,若采用插入排序算法,则时间和空间复杂度分别为(62);若采用快速排序算法,则时间和空间复杂度分别为(63)。A.O(n2)和O(n)B.O(n)和O(n)C.O(n2)和O(1)D.O(n)和O(1)

计算N!的递归算法如下,求解该算法的时间复杂度时,只考虑相乘操作,则算法的计算时间T(n)的递推关系式为(55);对应时间复杂度为(56)。int Factorial (int n){//计算n!if(n<=1)return 1;else return n * Factorial(n-1);}(62)A.T(n)=T(n-1)+1B.T(n)=T(n-1)C.T(n)=2T(n-1)+1D.T(n)=2T(n-1)-1

设某算法的计算时间表示为递推关系式T(n)=T(n-1)+n(n>O)及T(0)=1,则该算法的时间复杂度为(65)。A.O(lgn)B.O (nlgn)C.O(n)D.O(n2)

若某算法在问题规模为n时,其基本操作的重复次数可由下式表示,则该算法的时间复杂度为(64)。A.O(n)B.O(n2)C.O(logn)D.O (nlogn)

设一个广义表中结点的个数为n,则求广义表深度算法的时间复杂度为____。A.O(1)B.O(n)C.O(n2)D.O(log2n)

下面算法的时间复杂度为()A.O(1)B.O(n)C.O(n*n)D.O(n!)

设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n表示,则该算法的时间复杂度为(1)。A.O(lgn)B.O(nlgn)C.O(n)D.O(n2)

在某个算法时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算法的渐进时间复杂度为( ),若问题的规模增加了16倍,则运行时间增加( )倍。A.(n) B.(nlgn) C.(n2) D.(n2lgn) A.16 B.64 C.256 D.1024

求最短路径的FLOYD算法的时间复杂度为(16)。A.O(n)B.O(n+e)C.O(n2)D.O(n3)

设图G采用邻接表存储,则拓扑排序算法的时间复杂度为( )A.O(n)B.O(n+e)C.O(n2)D.O(n×e)

某个应用中,需要对输入数据进行排序,输入数据序列基本有序(如输入为1,2,5,3,4,6,8,7)。在这种情况下,采用( )排序算法最好,时间复杂度为(请作答此空)。A.O(n)B.O(nlgn)C.O(n^2)D.O(n^2lgn)

给定包含n个正整数的数组A和正整数x,要判断数组A中是否存在两个元素之和等于x,先用插入排序算法对数组A进行排序,再用以下过程P来判断是否存在两个元素之和等于x。low=1;high=n;while(high>low)if A[low]+A[high]=x return true;else if A[low]+A[high]>x low++;else high--;return false;则过程P的时间复杂度为( ),整个算法的时间复杂度为(请作答此空)。A.O(n)B.O(nlgn)C.O(n2)D.O(n2lgn)

某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算法的渐进时间复杂度为(62),若问题的规模增加了16倍,则运行时间增加(63)倍。A.16B.64C.256D.1024

某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算法的渐进时间复杂度为( ),若问题的规模增加了16倍,则运行时间增加(请作答此空)倍。A.16B.64C.256D.1024

已知算法A的运行时间函数为T(n)=8T(n/2)+n2,其中n表示问题的规模,则该算法的时间复杂度为( )A.θ(n)B.θ(nlgn)C.θ(n2)D.θ(n3)

设某算法的计算时间表示为递推关系式T(n)=T(n-1)+n(n>O)及T(0)=1,则该算法的时间复杂度为( )。A.O(lgn)B.O(nlgn)C.O(n)D.O(n^2)

某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算法的渐进时间复杂度为(62),若问题的规模增加了16倍,则运行时间增加(63)倍。 A.O(n)B.O(nlgn)C.O(n2)D.O(n2lgn)