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

server/2024/11/25 14:39:46/

目录

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

解答

首先明确边界值:

类型位数字节数左边界右边界
char8位1字节-128127
short16位2字节-3276832767
int32位4字节-21474836482147483647

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

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

-2147483648补码:10000000.00000000.00000000.00000000

(1)-i

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

i10000000000000000000000000000000
取反011111111111111111111111111111111
+110000000000000000000000000000000

因此-i仍为本身-2147483648

(2)~i

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

i10000000000000000000000000000000
取反011111111111111111111111111111111

(3)1-i

看作-i+1

-i10000000000000000000000000000000
100000000000000000000000000000001
-i+110000000000000000000000000000001

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

(4)-1-i

看作-i+(-1)

-i10000000000000000000000000000000
-111111111111111111111111111111111
-i+11011111111111111111111111

11111111

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


http://www.ppmy.cn/server/144817.html

相关文章

【含文档】基于django+Vue的荣誉证书管理系统(含源码+数据库+lw)

1.开发环境 开发系统:Windows10/11 架构模式:MVC/前后端分离 JDK版本: Java JDK1.8 开发工具:IDEA 数据库版本: mysql5.7或8.0 数据库可视化工具: navicat 主要技术: django,mysql,vue 2.视频演示地址 3.功能 系统定义了三个角色&#xff1a;管理员和学生和教师。 管理员进…

Linux-Apache静态资源

文章目录 静态资源权限设置 &#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f916;Linux专栏&#xff1a;点击&#xff01; ⏰️创作时间&#xff1a;2024年11月20日11点21分 静态资源 Apache配置静态资源 可以在网页上配置一个静态的FTP服务器&#xff0c;让用户…

安卓InputDispatching Timeout ANR 流程

1 ANR的检测逻辑有两个参与者: 观测者A和被观测者B&#xff0c;当然&#xff0c;这两者是不在同一个线程中的。2 A在调用B中的逻辑时&#xff0c;同时在A中保存一个标记F&#xff0c;然后做个延时操作C&#xff0c;延时时间设为T&#xff0c;这一步称为: 埋雷 。3 B中的逻辑如果…

设计自己的网络通信协议

文章目录 一、为什么需要设计网络通信协议1. **标准化通信规则**2. **确保数据传输的可靠性**3. **支持网络的多样性和可扩展性**4. **分层设计&#xff0c;简化复杂性**5. **实现设备的互操作性**6. **支持多任务和多应用并发**7. **提供安全性**8. **支持不同的通信模式**总结…

大数据实验4-HBase

一、实验目的 阐述HBase在Hadoop体系结构中的角色&#xff1b;能够掌握HBase的安装和配置方法熟练使用HBase操作常用的Shell命令&#xff1b; 二、实验要求 学习HBase的安装步骤&#xff0c;并掌握HBase的基本操作命令的使用&#xff1b; 三、实验平台 操作系统&#xff1…

【Docker集群应用】Docker基础与部署安装

文章目录 Docker概述Docker 与 虚拟机的区别Linux 六大命名空间Docker 的核心技术Docker 核心概念 Docker部署安装关闭防火墙和 SELinux安装依赖包设置阿里云镜像源安装 Docker-CE 并设置为开机自动启动查看 Docker 版本信息查看 Docker 信息Docker 系统信息 Docker 概述 Doc…

ctfshow-Misc入门(1-16)

misc1 查看图片得到flag misc2 1、打开文本&#xff0c;发现以“塒NG”开头 3、修改文件格式为png格式 4、查看图片&#xff0c;得到flag *遇到的问题&#xff1a;无法直接修改后缀名 *解决方法&#xff1a;需要点击文件夹&#xff0c;然后点击查看&#xff0c;将文件拓…

核心差异:知识VS文档管理(+工具软件安利)

在讨论知识管理和文档管理时&#xff0c;我们经常会听到这两种说法被混淆使用。然而&#xff0c;它们各自服务于不同的目的&#xff0c;这一点至关重要。 想象一下&#xff0c;你是一名项目经理&#xff0c;面临以下两项任务&#xff1a; 存储最新的项目计划捕捉团队讨论中获…