时间复杂度计算_求出下列算法的时间复杂度() int y=0; while((y+1)*(y-1)<=n) { y+

作者：木道寻08 | 2024-08-12 06:29:20

踩

求出下列算法的时间复杂度() int y=0; while((y+1)*(y-1)<=n) { y++; }

循环计算时间复杂度

循环计算时间复杂度分为单循环和多循环。在多循环计算时有部分可以直观看出，还有一部分需要进行等差等比数列的计算。

单循环

如下代码，两者皆是单循环，但是时间复杂度不同，第一个由于循环次数是已知的，因此时间复杂度是O(1)，而后者时间复杂度是O(n)。如果题目问计算次数，前者是100，后者是n。


for(i=0;i<100;i++)
    x++;
 
for(i=0;i<n;i++)
    y++;

在题目中时间复杂度一般不是持续+1，常见的时间复杂度计算如下。


O(logn):
for(i=1;i<=n;i*=2)
    x++;
 
while(i<=n)    i*=2;
-----------------------------------
O(sqrt(n)):
y=1;
while(y*y<=n)    y++;
 
i=0,sum=0;
while(sum<n)    sum+= ++i;    //等差数列

多循环

多循环可以两者的循环次数相同或是相关，两者循环边界相同可以直观的看出。如下代码，双重循环的循环起始都相同因此时间复杂度可以直接相乘，为O( $n^{2 }$ )。


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

有时候内循环的次数是与外循环直接相关的，因此不能直接相乘，需要通过等差等比数列来求和。可以将外层循环设置循环次数为k次并呈等比数列，因此 $k=log{n}$ ；内循环是等差数列，总循环次数为 $2^{k}$ 次。，带入内循环就是O(n)。


for(i=1;i<n;i*=2)
    for(j=0;j<i;j++)
        cnt++;

王道中有三重循环的题，可以将三重循环建立在空间坐标轴上，将它们理解为i是变量确定j，j确定后再确定k，那么由线到i-j组成等腰直角三角形，再到i-j-k行程单三棱柱。时间复杂度就是该柱体的体积O( $n^{3}$ )


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

递归计算时间复杂度

主定理

前提：a>=1,b>1.f(n)>0 满足一下的形式可以使用主定理，其中当n是常数时时间复杂度为O(1)，n大于该常数时带入公式。

$T\left ( n \right ) =\left\{\begin{matrix} O(1) \\ aT(\frac{n}{b})+f(n) \end{matrix}\right.$

判断O( $n^{\log_{b}{a}}$ )与O(f(n))大小，如果是大于则结果就是O( $n^{\log_{b}{a}}$ )，如下所示O( $n^{2 }$ )>O(1)所以时间复杂度就是O( $n^{2 }$ )。

$T\left ( n \right ) =\left\{\begin{matrix} 1 \\ 4T(\frac{n}{2})+1 \end{matrix}\right.$

如果等于则求出的结果乘 $\log{n}$ ，如下所示两边都为O(n)，因此时间复杂度需要乘上 $\log{n}$ ，结果为O( $n\log{n}$ )。

$T\left ( n \right ) =\left\{\begin{matrix} 1 \\ 2T(\frac{n}{2})+1 \end{matrix}\right.$

如果小于如下所示O( $\sqrt[]{n}$ )<O( $n^{3}$ ),那么需要额外再判断是否满足条件： $af(\frac{n}{b})\le cf(n)$ , $c\le1$ 。由于 $c\le1$ 存在，所以最终结果为O( $n^{3}$ )

$T\left ( n \right ) =\left\{\begin{matrix} 1 \\ 4T(\frac{n}{2})+n^{^{3} } \end{matrix}\right.$

树状图

当b=1时主定理不能使用，采用树状图来求时间复杂度。时间复杂度为：叶子数 + f(n) * 层数.

如下所示，其递归形成的数据结构可以理解为单链表，所以叶子数为1，层数为n，f(n)=n时间复杂度为O( $n^{2 }$ )

$T(n)=T(n-1)+n$

此结构为二叉树，叶子结点为 $2^{n}$ ，层数和f(n)都为n，所以时间复杂度为：O( $2^{n}+n^{2}$ )舍去后为O( $2^{n }$ )

$T(n)=2T(n-1)+n$

参考来自B站视频，本文可能存在理解或是输入问题，可以直接参考视屏作者视频。该视频存在一处错误在评论区已指正。https://www.bilibili.com/video/BV1Jh4y1k7Bh/?spm_id_from=333.337.search-card.all.click&vd_source=cfeac22c9575f1b5d3c53eba5479060d

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/木道寻08/article/detail/968145