数据结构与算法——1120——时间空间效率问题&&求边界值
目录
3、O(n²) 或O(n*log2n)——n倍的log以2为底n的对数
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
解答
首先明确边界值：
| 类型 | 位数 | 字节数 | 左边界 | 右边界 |
| char | 8位 | 1字节 | -128 | 127 |
| short | 16位 | 2字节 | -32768 | 32767 |
| int | 32位 | 4字节 | -2147483648 | 2147483647 |
i和-i的补码值相同，均为10000000.00000000.00000000.00000000
由此可知，-2147483648为int型可表示的最小值，因此符号位取1，其余全0
-2147483648补码：10000000.00000000.00000000.00000000
（1）-i
-i补码算法：将i所有位取反+1
| i | 10000000 | 00000000 | 00000000 | 00000000 |
| 取反 | 011111111 | 11111111 | 11111111 | 11111111 |
| +1 | 10000000 | 00000000 | 00000000 | 00000000 |
因此-i仍为本身-2147483648
（2）~i
~i为全部取反，为01111111.11111111.11111111.11111111，为2147483647
| i | 10000000 | 00000000 | 00000000 | 00000000 |
| 取反 | 011111111 | 11111111 | 11111111 | 11111111 |
（3）1-i
看作-i+1
| -i | 10000000 | 00000000 | 00000000 | 00000000 |
| 1 | 00000000 | 00000000 | 00000000 | 00000001 |
| -i+1 | 10000000 | 00000000 | 00000000 | 00000001 |
结果为2147483649，因为溢出，所以应为-2147483647
（4）-1-i
看作-i+(-1)
| -i | 10000000 | 00000000 | 00000000 | 00000000 |
| -1 | 11111111 | 11111111 | 11111111 | 11111111 |
| -i+1 | 101111111 | 11111111 | 11111111 | 11111111 |
此时最前面的1溢出，因此结果为01111111.11111111.11111111.11111111，为2147483647
原文地址：https://blog.csdn.net/weixin_74681777/article/details/143997007
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！