时间复杂度和空间复杂度的计算_循环函数的空间复杂度

作者：盐析白兔 | 2024-08-20 21:03:33

踩

循环函数的空间复杂度

1.时间复杂度

1.1一层循环

1.1.1解题思路

列出循环趟数t和每轮循环i的值
找到t与i的关系
确定循环停止条件
联立解方程
写结果

1.1.2举例

求时间复杂度


i = n*n;
while(i!=1)
    i /= 2;

t 0 1 2

i $n^2$ $\frac{n^2}{2}$ $\frac{n^2}{4}$

t与i的关系： $i = \frac{n^2}{2^{t}}$

循环停止条件：i=1

有 $\frac{n^2}{2^t}=1$

$t=2log_2n$ 及复杂度为 $O(log_2n)$

1.2两层循环

1.2.1解题思路_计算

列出外层循环i的变化值
列出内层语句的执行次数
求和，写结果

1.2.1解题思路2_面积法

1.2.2举例

求时间复杂度


for(i=0;i<n;i++)
    for(j=0;j<m;j++)
        t++;

计算

i 0 1 2 ... n-1

m m m ... m

时间复杂度为O(mn)

面积

mn

1.3多层循环

1.1.1解题思路

体积法
计算

1.1.2举例

求时间复杂度


for(i=0;i<=n;i++)
    for(j=0;j<=i;j++)
        for(k=0;k<=j;k++)
            t++;

体积

$n^3$

计算

$\sum_{i=0}^{n}\sum_{j=0}^{i}\sum_{k=0}^{j-1}1 = O(n^3)$

2.空间复杂度

1、常量空间
存储空间大小固定，和输入没有关系，空间复杂度是O(1)

2、线性空间
算法中定义了一个线性集合，如一个列表，并且集合大小和输入规模n成正比，空间复杂度记为O(n)

3、二维空间
算法中定义了一个二维列表集合，并且集合的长和宽都和输入规模n成正比，空间复杂度记为O（nm)

4、递归空间
递归过程就是一个进栈和出栈的过程，当进入一个新函数时，进行入栈操作，把调用的函数和参数信息压入栈中；当函数返回时，执行出栈。
递归的空间复杂度也是线性的，如果递归的深度是n，那么空间复杂度就是O(n)。

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