数据结构与算法——1120——时间空间效率问题求边界值

目录

1、效率问题

1、时间复杂度

1、O(1)

2、O(n)

3、O(n²) 或O(n*log2n)——n倍的log以2为底n的对数

例题

4、O(n³)

2、空间复杂度

3、数组和链表

2、面试题之求边界值

题目

解答

（1）-i

（2）~i

（3）1-i

（4）-1-i

1、效率问题

效率问题与变化有关

效率排序：常对幂指阶

1、时间复杂度

定义：内存访问次数，或代码的总运行次数

1、O(1)

表示当前代码的时间消耗为常量，在有限可数的资源范围内可以完成

即：消耗的资源不受输入数据量n的影响

2、O(n)

表示一层循环

for(i=1;i<=n;i++)
{
    cout<<i<<endl;
}

3、O(n²) 或O(n*log2n)——n倍的log以2为底n的对数

表示两层嵌套问题

例题

1、O(n²)

for(i=1;i<=n;i++)
{
    for(j=1;j<=n;j++)
    {
        cout<<j<<endl;
    }
}

i=n时，代码从1-n执行了n次；i=2时，同样执行了n次；以此类推，一直到i=n时，共执行了n²次

 2、O(n*log2n)

for(i=1;i<=n;i++)
{
    for(j=1;j<=n;j*2)
    {
    cout<<j<<endl;
    }
}

1*2*2*2*......*2=n；即：2的k次方=n，k=log以2为底n的对数

4、O(n³)

表示三层嵌套问题

for(i=1;i<=n;i++)
{
    for(j=1;j<=n;j*2)
    {
        for(k=1;k<=j;k++)
        {
            cout<<k<<endl;
        }
    }
}

i=1时，时间复杂度为1；i=2时，为1+2；i=3时，1+2+3；i=4时；1+2+3+4......,则总时间复杂度为

≈n³

2、空间复杂度

空间复杂度：为了额外解决问题而额外消耗的空间

如果消耗的空间不随着输入数据量的变化而变化，则空间复杂度为O(1)

3、数组和链表

数组：类型相同（想要类型不同的，因此出现了结构体、类），空间连续，长度固定（增删难）

链表：增删快，但要付出查找的代价

2、面试题之求边界值

题目

在C语言中，存在int i=-2147483648，求-i，~i，1-i，-1-i

解答

首先明确边界值：

i和-i的补码值相同，均为10000000.00000000.00000000.00000000

由此可知，-2147483648为int型可表示的最小值，因此符号位取1，其余全0

-2147483648补码：10000000.00000000.00000000.00000000

（1）-i

-i补码算法：将i所有位取反+1

因此-i仍为本身-2147483648

（2）~i

~i为全部取反，为01111111.11111111.11111111.11111111，为2147483647

（3）1-i

看作-i+1

结果为2147483649，因为溢出，所以应为-2147483647

（4）-1-i

看作-i+(-1)

此时最前面的1溢出，因此结果为01111111.11111111.11111111.11111111，为2147483647