数据结构(空间复杂度介绍)超详细!!!

1. 数据结构前言

1.1 数据结构

数据结构是计算机存储、组织数据的形式,指相互之间存在一种或多种特定关系的数据元素的集合

1.2 算法

算法:良好的计算过程,它取一个或一组的值为输入,并产生出一个或一组的值作为输出。即算法经过一系列的计算步骤,用来将输入数据转化成输出结果。

2. 总结

数据结构与算法在校园招聘笔试和面试都具有重要的地位,因此学会它是必要的。

2. 算法效率

2.1 复杂度概念

算法在编写成可执行程序后,运行时需要耗费时间资源和空间资源。

时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。随着时代的发展,计算机的容量得到了较快的发展,因此一个算法不在特别关注空间复杂度。

3. 时间复杂度

定义:算法的时间复杂度是一个函数式T(N),它定量描述该算法的运行时间。时间复杂度是衡量的时间效率,为什么不计算程序运行时间。

那么算法的时间复杂度是⼀个函数式T(N)到底是什么呢?这个T(N)函数式计算了程序的执⾏次数。通 过c语⾔编译链接章节学习,我们知道算法程序被编译后⽣成⼆进制指令,程序运⾏,就是cpu执⾏这 些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执⾏次数的函数式T(N),假设每 句指令执⾏时间基本⼀样(实际中有差别,但是微乎其微),那么执⾏次数和运⾏时间就是等⽐正相关, 这样也脱离了具体的编译运⾏环境。执⾏次数就可以代表程序时间效率的优劣。⽐如解决⼀个问题的 算法a程序T(N) = N,算法b程序T(N) = N^2,那么算法a的效率⼀定优于算法b。
案例
// 请计算⼀下 Func1 ++count 语句总共执⾏了多少
次?
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
}
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
}

实际中我们计算时间复杂度时,计算的也不是程序的精确的执⾏次数,精确执⾏次数计算起来还是很 ⿇烦的(不同的⼀句程序代码,编译出的指令条数都是不⼀样的),计算出精确的执⾏次数意义也不⼤, 因为我们计算时间复杂度只是想⽐较算法程序的增⻓量级,也就是当N不断变⼤时T(N)的差别,上⾯我 们已经看到了当N不断变⼤时常数和低阶项对结果的影响很⼩,所以我们只需要计算程序能代表增⻓量 级的⼤概执⾏次数,复杂度的表⽰通常使⽤⼤O的渐进表⽰法。

3.1 大O渐进表示法

大O符号:用于描述函数渐进行为的数学符号。

通过以上⽅法,可以得到 Func1 的时间复杂度为: O ( N 2 )

3.2 时间复杂度计算实例

3.2.1 实例1

// 计算 Func2 的时间复杂度?
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n", count);
}
Func2执行的基本操作次数:
T(N)=2N+10
根据推导规则第二条得出
Func2的时间复杂度为:O(N)

3.2.2 实例2

// 计算 Func3 的时间复杂度?
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++ k)
{
++count;
}
for (int k = 0; k < N ; ++
k)
{
++count;
}
printf("%d\n", count);
}
Func3执行的基本操作次数:
T(N)=N+M
Func2的时间复杂度为:O(N +M)

3.2.3 实例3

// 计算 Func4 的时间复杂度?
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}
Func4执行的基本操作次数:
T(N)=100
根据推导规则第三条得出
Func2的时间复杂度为:O(1)

3.2.4 实例4

// 计算 strchr 的时间复杂度?
const char * strchr ( const char
* str, int character)
{
const char * p_begin = s;
while (*p_begin != character)
{
if (*p_begin == '\0' )
return NULL ;
p_begin++;
}
return p_begin;
}

strchr执⾏的基本操作次数:
1)若要查找的字符在字符串第⼀个位置,则:
T ( N ) = 1
2)若要查找的字符在字符串最后的⼀个位置,
则:
T ( N ) = N
3)若要查找的字符在字符串中间位置,则:
T ( N ) =
2
N
因此:strchr的时间复杂度分为:
最好情况: O (1)
最坏情况: O ( N )
平均情况: O ( N )

3.2.5 实例5

// 计算 BubbleSort 的时间复杂度?
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
1)若数组有序,则:
T ( N ) = N
2)若数组有序且为降序,则:
T ( N ) = N ∗ ( N + 1)/2
3)若要查找的字符在字符串中间位
置,则:
因此:BubbleSort的时间复杂度取最
差情况为: O ( N 2 )

3.2.6 实例6

void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
当n=2时,执⾏次数为1
当n=4时,执⾏次数为2
当n=16时,执⾏次数为4
假设执⾏次数为 x ,则 2 x = n
因此执⾏次数: x = log n
因此:func5的时间复杂度取最差情况为: O (log 2 n )

3.2.7 实例7

// 计算阶乘递归 Fac 的时间复杂度?
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}
调⽤⼀次Fac函数的时间复杂度为 O (1)
⽽在Fac函数中,存在n次递归调⽤Fac函数
因此:阶乘递归的时间复杂度为: O ( n )

4. 空间复杂度

空间复杂度也是⼀个数学表达式,是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。空间复杂度不是程序占⽤了多少bytes的空间,因为常规情况每个对象⼤⼩差异不会很⼤,以空间复 杂度算的是变量的个数。 空间复杂度计算规则基本跟实践复杂度类似,也使⽤⼤O渐进表⽰法。 注意:函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好 了,因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定。

4.1 空间复杂度示例

4.1.1 实例1

// 计算 BubbleSort 的时间复杂度?
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
函数栈帧在编译期间已经确定好了, 只需要关注函数在运⾏时额外申请的 空间。
BubbleSort额外申请的空间有 exchange等有限个局部变量,使⽤了常数个额外空间 因此空间复杂度为 O (1)

4.1.2 实例2

// 计算阶乘递归 Fac 的空间复杂度?
long long Fac(size_t N)
{
if(N == 0)
return 1;
return Fac(N-1)*N;
}
Fac递归调⽤了N次,额外开辟了N个函数栈帧, 每个栈帧使⽤了常数个空间 ,因此空间复杂度为: O ( N )

5. 常见复杂度对比

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/376441.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

UART编程

Q:为什么使用串口前要先在电脑上安装CH340驱动&#xff1f; 中断的作用&#xff1f; 环形buffer的作用&#xff1f; static和valitate的作用 三种编程方式简介 也可以通过DMA方式减小CPU资源的消耗 直接把数据在SRAM内存和UART模块进行传输 &#xff0c;流程&#xff1a; …

css文字自适应宽度动态出现省略号...

前言 在列表排行榜中通常会出现的一个需求&#xff1a;从左到右依次是名次、头像、昵称、徽标、分数。徽标可能会有多个或者没有徽标&#xff0c;徽标长度是动态的&#xff0c;昵称如果过长要随着有无徽标进行动态截断出现省略号。如下图布局所示&#xff08;花里胡哨的底色是…

接口安全配置

问题点&#xff1a; 有员工在工位在某个接口下链接一个集线器&#xff0c;从而扩展上网接口&#xff0c;这种行为在某些公司是被禁止的&#xff0c;那么网络管理员如何控制呢&#xff1f;可以配置接口安全来限制链接的数量&#xff0c;切被加入安全的mac地址不会老化&#xff…

防火墙NAT智能选举综合实验

一、实验目的 1&#xff0c;办公区设备可以通过电信链路和移动链路上网(多对多的NAT&#xff0c;并且需要保留一个公网IP不能用来转换) 2&#xff0c;分公司设备可以通过总公司的移动链路和电信链路访问到Dmz区的http服务器 3&#xff0c;多出口环境基于带宽比例进行选路&…

Anaconda+Pycharm 项目运行保姆级教程(附带视频)

最近很多小白在问如何用anacondapycharm运行一个深度学习项目&#xff0c;进行代码复现呢&#xff1f;于是写下这篇文章希望能浅浅起到一个指导作用。 附视频讲解地址&#xff1a;AnacondaPycharm项目运行实例_哔哩哔哩_bilibili 一、项目运行前的准备&#xff08;软件安装&…

护网HW面试常问——组件中间件框架漏洞(包含流量特征)

apache&iis&nginx中间件解析漏洞 参考我之前的文章&#xff1a;护网HW面试—apache&iis&nginx中间件解析漏洞篇-CSDN博客 log4j2 漏洞原理&#xff1a; 该漏洞主要是由于日志在打印时当遇到${后&#xff0c;以:号作为分割&#xff0c;将表达式内容分割成两部…

Linux的世界 -- 初次接触和一些常见的基本指令

一、Linux的介绍和准备 1、简单介绍下Linux的发展史 1991年10月5日&#xff0c;赫尔辛基大学的一名研究生Linus Benedict Torvalds在一个Usenet新闻组(comp.os.minix&#xff09;中宣布他编制出了一种类似UNIX的小操作系统&#xff0c;叫Linux。新的操作系统是受到另一个UNIX的…

WGCLOUD的ping设备监测可以导入excel数据吗

可以的 WGCLOUD的v3.5.3版本&#xff0c;已经支持导入excel数据&#xff0c;如下说明 数通设备PING监测使用说明 - WGCLOUD

FreeRTOS学习(1)STM32单片机移植FreeRTOS

一、FreeRTOS源码的下载 1、官网下载 FreeRTOS官方链接 官方下载速度慢&#xff0c;需要翻墙&#xff0c;一般选择第一个 2、直接通过仓库下载 仓库地址链接 同样很慢&#xff0c;甚至打不开网页&#xff0c;也不建议使用这种方法。 3、百度网盘 链接&#xff1a;https:…

Java | Leetcode Java题解之第234题回文链表

题目&#xff1a; 题解&#xff1a; class Solution {public boolean isPalindrome(ListNode head) {if (head null) {return true;}// 找到前半部分链表的尾节点并反转后半部分链表ListNode firstHalfEnd endOfFirstHalf(head);ListNode secondHalfStart reverseList(firs…

百度智能云将大模型引入网络故障定位的智能运维实践

物理网络中&#xff0c;某个设备发生故障&#xff0c;可能会引起一系列指标异常的告警。如何在短时间内从这些告警信息中找到真正的故障原因&#xff0c;犹如大海捞针&#xff0c;对于运维团队是一件很有挑战的事情。 在长期的物理网络运维工作建设中&#xff0c;百度智能云通…

OpenCV距离变换函数distanceTransform的使用

操作系统&#xff1a;ubuntu22.04OpenCV版本&#xff1a;OpenCV4.9IDE:Visual Studio Code编程语言&#xff1a;C11 功能描述 distanceTransform是OpenCV库中的一个非常有用的函数&#xff0c;主要用于计算图像中每个像素到最近的背景&#xff08;通常是非零像素到零像素&…

数据结构(4.1)——串的存储结构

串的顺序存储 串&#xff08;String&#xff09;的顺序存储是指使用一段连续的存储单元来存储字符串中的字符。 计算串的长度 静态存储(定长顺序存储) #define MAXLEN 255//预定义最大串为255typedef struct {char ch[MAXLEN];//每个分量存储一个字符int length;//串的实际长…

【机器学习】精准农业新纪元:机器学习引领的作物管理革命

&#x1f4dd;个人主页&#x1f339;&#xff1a;Eternity._ &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; ❀目录 &#x1f50d;1. 引言&#x1f4d2;2. 精准农业的背景与现状&#x1f341;精准农业的概念与发展历程&#x1f342;国内外精准农业实践案…

MySQL-ubuntu环境下安装配置mysql

文章目录 什么是数据库&#xff1f;一、ubuntu环境下安装mysql二、配置mysql配置文件1.先登上root账号2.配置文件的修改show engines \G; mysql和mysqld数据库的基础操作登录mysql创建数据库显示当前数据库使用数据库创建表插入students表数据打印students表数据select * from …

自动驾驶中的人机互相接管问题讨论

一、背景 人机接管&#xff08;human takeover&#xff09;是指在自动驾驶过程中&#xff0c;当系统遇到超出其处理能力或预设安全阈值的情况时&#xff0c;将控制权交还给驾驶员的过程。这一环节的设计直接关系到自动驾驶技术的实用性与安全性&#xff0c;是目前研究和实践中…

RequestContextHolder多线程获取不到request对象

RequestContextHolder多线程获取不到request对象&#xff0c;调用feign接口时&#xff0c;在Feign中的RequestInterceptor也获取不到HttpServletRequest问题解决方案。 1.RequestContextHolder多线程获取不到request对象 异常信息&#xff0c;报错如下&#xff1a; 2024-07-0…

Linux:Linux网络总结(附下载链接)

文章目录 下载链接网络问题综合问题访问一个网页的全过程&#xff1f;WebSocket HTTPHTTP基本概念GET与POSTHTTP特性HTTP缓存技术HTTP的演变HTTP1.1 优化 HTTPSHTTP与HTTPS有哪些区别&#xff1f;HTTPS解决了HTTP的哪些问题&#xff1f;HTTPS如何解决的&#xff1f;HTTPS是如何…

鸿蒙系统在服装RFID管理中的应用:打造智能零售新时代

​随着物联网技术的迅速发展&#xff0c;服装零售行业正面临着新的变革与挑战。鸿蒙系统作为新一代智能操作系统&#xff0c;结合RFID技术&#xff0c;为服装行业提供了高效、智能的管理解决方案。常达智能物联&#xff0c;作为RFID技术的领先企业&#xff0c;致力于将鸿蒙系统…

每日一练:奇怪的TTL字段(python实现图片操作实战)

打开图片&#xff0c;只有四种数字&#xff1a;127&#xff0c;191&#xff0c;63&#xff0c;255 最大数字为255&#xff0c;想到进制转换 将其均转换为二进制&#xff1a; 发现只有前2位不一样 想着把每个数的前俩位提取出来&#xff0c;组成新的二进制&#xff0c;然后每…