递推公式求算法的时间复杂度

⑴ 这个算法的时间复杂度是如何计算出来的

如果题目允许优化程序的话，计算X的多次幂时可以保留中间结果，比如你已经有了X^3，计算X^4的时候就不用从头乘一遍，也不用二分着来，直接X^3在乘X就可以了。如果采用这样的策略，这题是可以以O(N)实现的。

如果不考虑上面所说，复杂度是NlogN，你的计算过程可行。另外也可估算，即单次求幂是logN，求N次就是NlogN，这样估出来的是上界。但是在不保留中间结果的算法下，是无法达成O（N）的，故可以不严谨地“直觉”知道下界也是NlogN。

⑵ 如何计算一个算法的时间复杂度

求解算法的时间复杂度的具体步骤是：

1、找出算法中的基本语句：

算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

2、计算基本语句的执行次数的数量级：

（1）只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。

（2）这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。

3、用大Ο记号表示算法的时间性能：

（1）将基本语句执行次数的数量级放入大Ο记号中。

（2）如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：

for(i=1;i<=n;i++)x++;for(i=1;i<=n;i++)
for(j=1;j<=n;j++)x++;

（3）第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。

⑶ 算法的时间复杂度的计算

n的平方*2
1.比较次数：
i:n-1约等于n
j:1+2+3+……+(n-1)=(n方-n)/2
总：n+(n方-n)/2=（n方+n）/2
2.加法运算次数
i：约为n
j：(n方-n)/2
x：(n方-n)/2
总：相加得n方
3.赋值运算次数
a[i][j]：(n方-n)/2

总的时间复杂度约为
（n方+n）/2+n方+(n方-n)/2=2n方

⑷ 快速排序时间复杂度递推式求通项公式~

两边同除以n(n+1)得到
C(n)/(n+1) = 2/(n+1) + C(n-1)/n
然后取n=1,2,...求和得到
C(n)/(n+1) = 2(1/2+...+1/(n+1)) + O(1) = 2lnn + O(1)
所以C(n)=2nlnn + O(n)

⑸ 设某算法的计算时间表示位递推关系式T(n)=T(n-1)+n(n位正整数)及T(0)=1,则该算法的时间复杂度为

选择D.

T(n)
=T(n-1)+n
=T(n-2)+(n-1)+n
=T(n-3)+(n-2)+(n-1)+n
...
=T(0)+1+2+...+(n-2)+(n-1)+n
=1+1+2+...+(n-2)+(n-1)+n
=1+(n+1)*n/2
所以为 O(n²)，选D。

⑹ 根据递推公式求算法时间复杂度

这题还有另一种，可以参考MIT 算法导论，你们图书馆肯定有的，网上可以找到电子版。

或者搜索算法导论的PPT也可以。

⑺ 求算法的时间复杂度，要详细推导过程，循环次数

⑻ 若某算法的计算时间表示为递推关系式:T(N)=2T(N/2)+NlogN T(1)=1则该算法的时间复杂度为

利用分叉树来做，根结点nlogn，每次下分两个子树，结点为n/2logn/2，一直做到最后，发现最后的log里面的真数为1，也就是0。对每一层加和，第一层nlogn，第二层nlogn/2也就是nlogn-nlog2，以此类推，nlogn-nlog4，nlogn-nlog8，....,nlogn-nlogn。树高以2为底logn，乘进去为nlogn*logn - n/2*logn -n/2*(logn)^2,就是O（n（logn）^2）。（手机网络回答不会插入图片，我是这么做的，有错误还请指出）

⑼ 怎么求算法的时间复杂度

for( i=1; i<=n; i++)
这个语句的时间复杂度也是n， i 的值分别为 1,2,3, ..., n
但是，一般算时间复杂度这几个都会近似地看成O(n)，常数一般会忽略不计（除非很大的情况下）

⑽ 请问递归算法的时间复杂度如何计算呢

递归算法的时间复杂度在算法中，当一个算法中包含递归调用时，其时间复杂度的分析会转化为一个递归方程求解，常用以下四种方法：

1.代入法(Substitution Method)

代入法的基本步骤是先推测递归方程的显式解，然后用数学归纳法来验证该解是否合理。

2.递归程序设计是程序设计中常用的一种方法，它可以解决所有有递归属性的问题，并且是行之有效的.

3.但对于递归程序运行的效率比较低，无论是时间还是空间都比非递归程序更费，若在程序中消除递归调用，则其运行时间可大为节省.