进入数据结构的世界
数据结构和算法的概述
- 一、什么是数据结构
- 二、什么是算法
- 三、如何去学习数据结构和算法
- 四、算法的时间复杂度和空间复杂度
- 4.1 算法效率
- 4.2 大O的渐进表示法
- 4.3 时间复杂度
- 4.4 空间复杂度
- 4.5 常见复杂度对比
一、什么是数据结构
数据结构是计算机存储、组织数据的方式。(相互之间存在一种或多种特定关系的数据元素的集合)
二、什么是算法
算法就是一系列的计算步骤,用来吧输入数据转换成输出结果。(算法就是有良好的计算过程,把一个或一组的值输入,并产出一个或一组的值输出)
三、如何去学习数据结构和算法
现在的公司对学生的代码能力越来越高,数据结构和算法的题目越来越难。算法的能力在短期内是不能够快速提升的,需要进行算法训练的积累。校招的时候,笔试很难,为了能够找到工作,还需要对数据结构和算法早早的准备,多去训练算法能力。
数据结构和算法对于初学者来说很难。但 是,古话说的好,世上无难事,只怕有心人。不管数据结构和算法有多难,我们都要硬着头皮去学。我相信,只要多学多练,学习数据结构和算法就会越来越简单。
四、算法的时间复杂度和空间复杂度
时间和空间这两个维度能够衡量算法的好坏,
4.1 算法效率
算法在编写成可执行程序后,运行程序需要耗费空间资源和时间资源。因此,衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,这就是时间复杂度和空间复杂度。
时间复杂度主要是衡量算法的运行快慢,而空间复杂度主要是衡量一个算法运行时所需要的额外空间。(计算机发展的早期,计算机存储的容量很小,我们对空间复杂度很在乎。但是经过计算机行业的快速发展,计算机存储的容量已经达到了很高的地步。所以我们今天已经不需要特别在关注算法的空间复杂度)
4.2 大O的渐进表示法
大O符号(Big O notation):用于描述函数渐进行为的数学符号
大O的渐进表示法的推导方法:
1、用常数1取代运行时间中所以的加法常数。
2、在运行次数函数中,只保留最高阶项。
3、如果最高价项存在且不是1,则去除与这个项相乘的常数,得到的结果就是大O阶。
算法的时间复杂度存在最好、平均和最坏情况:
最好情况:任意输入规模的最大运行次数(上界)
平均情况:任意输入规模的期望运行次数
最坏情况:任意输入规模的最小运行次数(下界)
例如:在一个长度为N的数组中搜索一个数据x
最好情况:1次找到
平均情况:N/2次找到
最坏情况:N次找到
实际中,我们关注的都是算法的最坏情况。所以,数组中搜索数据的时间复杂度为O(N)
4.3 时间复杂度
时间复杂度的定义:
一个算法执行所消耗的时间,从理论上说,是不能够算出来得,只有把程序放在机器上跑,才能够知道消耗的时间。一个算法所花费的时间与其中语句的执行次数成正比,算法的基本操作的执行次数,就是算法的时间复杂度。
案例1:
找到基本语句与问题规模n的数学表达式,算出该算法的时间复杂度。
//计算++count语句执行的次数
#include <stdio.h>
int main()
{int n = 0;scanf("%d", &n);int count = 0;for (int i = 0; i < n; i++){for (int j = 0; j < n; j++)++count;}for (int i = 0; i < 2 * n; i++){++count;}int m = 10;while (m--){++count;}printf("%d\n", count);return 0;
}
基本操作次数:
F(n)=n^2+2*n+10
- n=10 F(n)=130
- n=100 F(n)=10210
- n=1000 F(n)=1002010
用大O的渐进表示法,时间复杂度为O(N^2)
- n=10 F(n)=100
- n=100 F(n)=10000
- n=1000 F(n)=1000000
实际中我们计算时间复杂度时,并不一定计算精准的时间复杂度,而只需要大概执行次数,这里我们使用大O的渐进表示法。
通过上面我们可以发现大O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。
案例2:
计算Fun2的时间复杂度
void Fun2()
{int N;scanf("%d", &N);int count = 0;for (int i = 0; i < 2 * N; i++){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}
Fun2的时间复杂度为:
F(N)=2*N+10
大O的渐进表示法:时间复杂度为O(N)
案例3:
//计算Fun3的时间复杂度
void Fun3()
{int N, M;scanf("%d%d", &N, &M);int count = 0;for (int i = 0; i < N; i++){++count;}for (int j = 0; j < M; j++){++count;}printf("%d\n", count);
}
Fun2的时间复杂度为:
F(N)=N+M
大O的渐进表示法:时间复杂度为O(N)
案例4:
//二分查找的思想
void Fun4()
{int m = 0;int arr[10] = { 1,2,4,6,8,11,55,66,77,88};int n;printf("请输入要查找的数:\n");scanf("%d", &n);int begin = 0;int end = 9;while (begin <= end){int mid = begin + (end - begin)/2;if (arr[mid] < n)begin = mid + 1;else if (arr[mid] > n)end = mid - 1;else{printf("找到了\n");printf("%d", arr[mid]);m = 1;break;}}if(m==0)printf("没找到\n");
}
区间数据个数:
N
N/2
N/2/2
…………
N/2/2/2……/2=1
最坏的情况,查找区间缩放只剩一个值时,就是坏得,
假设查找x次,2^x=N,所以x=logN。
大O的渐进表示法:时间复杂度为O(logN).
案例5:
//斐波那契递归的复杂度
#include <stdio.h>
int Fun5(size_t n)
{if (n < 3)return 1;return Fun5(n - 2) + Fun5(n - 1);}
int main()
{int n = 7;int sum=Fun5(n);printf("%d\n", sum);return 0;
}
打印结果:

递归展开图:

1次(2^ 0)
2次(2^ 1)
4次(2^ 2)
8次(2^ 3)
……
2^(N-1)次
通过函数递归图分析基本操作递归了2 ^N-1次,
大O的渐进表示法:时间复杂度为O (2 ^N)。
4.4 空间复杂度
空间复杂度的定义:
一个算法在运行过程中临时占用存储空间大小的量度。(空间复杂度算的是变量的个数)
注意:
函数运行时所需要的栈空间(存储函数、局部变量、一些寄存器信息等)在编译期间就已经确定好了,因此,空间复杂度主要就是函数在运行的时候申请的额外空间来确定的。
案例1:
//计算BubbleSort函数的空间复杂度
void BubbleSort(int* a, int n)
{assert(a);for (int end = n; end > 0; end--){int exchange = 0;for (int i = 1; i < n; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}//不需要循环了if (exchange == 0)break;}
}
可以看出使用了常数个额外空间,所以空间复杂度为O(1)
案例2:
//看返回斐波那契数列的前n项,计算Fibonac的空间复杂度
int* Fibonac(int n)
{if (n == 0)return NULL;int* fibar = (int*)malloc(sizeof(int) * (n + 1));fibar[0] = 0;fibar[1] = 1;for (int i = 2; i <= n; i++){fibar[i] = fibar[i - 1] + fibar[i - 2];}return fibar[i];
}
动态开辟了n+1个空间,大O的渐进表示法为O(N);
4.5 常见复杂度对比


相关文章:
进入数据结构的世界
数据结构和算法的概述 一、什么是数据结构二、什么是算法三、如何去学习数据结构和算法四、算法的时间复杂度和空间复杂度4.1 算法效率4.2 大O的渐进表示法4.3 时间复杂度4.4 空间复杂度4.5 常见复杂度对比 一、什么是数据结构 数据结构是计算机存储、组织数据的方式。&#x…...
stm32之看门狗
STM32 有两个看门狗,独立看门狗和窗口看门狗,独立看门狗又称宠物狗,窗 口看门狗又称警犬。可用来检测和解决由软件错误引起的故障。两个看门狗的原理都是当计数器达到给定的超时值时,产生系统复位,对于窗口型看门狗同…...
纤维蛋白单体(FM)介绍
纤维蛋白单体(FM)是血栓形成的早期产物,是纤维蛋白原(Fibrinogen,Fbg)在凝血酶(Thrombin)的作用下,脱掉肽A(Fibrinopeptide A,Fp A)与…...
知识图谱实战导论:从什么是KG到LLM与KG/DB的结合实战
前言 本文侧重讲解: 什么是知识图谱LLM与langchain/数据库/知识图谱的结合应用 比如,虽说基于知识图谱的问答 早在2019年之前就有很多研究了,但谁会想到今年KBQA因为LLM如此突飞猛进呢 第一部分 知识图谱入门导论 //待更.. 第二部分 LLM与…...
第5章 会话与会话技术
第5章 会话与会话技术 一. 单选题(共5题,50分)二. 判断题(共5题,50分) 一. 单选题(共5题,50分) (单选题) 阅读下面代码: Book book BookDB.getBook(id)…...
IDEA2023新UI回退老UI
idea2023年发布了新UI,如下所示 但是用起来真心不好用,各种位置也是错乱,用下面方法可以回退老UI...
ElasticSearch(三)
1.数据聚合 聚合(aggregations)可以让我们极其方便的实现对数据的统计、分析、运算。例如: 什么品牌的手机最受欢迎? 这些手机的平均价格、最高价格、最低价格? 这些手机每月的销售情况如何? 实现这些…...
【LinkedHashMap】146. LRU 缓存
146. LRU 缓存 解题思路 与普通的 HashMap 不同,LinkedHashMap 会保持元素的有序性。这可以在某些情况下提供更可预测的迭代顺序直接获取元素 因为使用到该元素 将该元素重新放入队尾 表示最近使用该元素写入元素,首先如果该元素原来存在 那么需要将ke…...
Opencv-python去图标与水印方案实践
RGB色彩模式是工业界的一种颜色标准,是通过对红(R)、绿(G)、蓝(B)三个颜色通道的变化以及它们相互之间的叠加来得到各式各样的颜色的,RGB即是代表红、绿、蓝三个通道的颜色ÿ…...
自己写过比较蠢的代码:从失败中学习的经验
文章目录 引言1. 代码没有注释2. 长函数和复杂逻辑3. 不恰当的变量名4. 重复的代码5. 不适当的异常处理6. 硬编码的敏感信息7. 没有单元测试结论 🎉 自己写过比较蠢的代码:从失败中学习的经验 ☆* o(≧▽≦)o *☆嗨~我是IT陈寒🍹✨博客主页&a…...
C语言 cortex-A7核 点LED灯 (附 汇编实现、使用C语言 循环实现、使用C语言 封装函数实现【重要、常用】)
1 汇编实现 text global _start start: ************** LED1点灯 ---> PE10 **************/ ************** RCC章节初始化 **************/ CC_INIT:1.使能GPIOE组控制器,通过RCC_MP_AHB4ENSETR寄存器设置GPIOE组使能0x50000A28[4] 1ldr r0,0x50000A28 准…...
LABVIEW 实战案例1--温度报警系统
图1 温度报警系统前面板 图2 温度报警系统后面板...
【力扣】292. Nim 游戏
题目描述 你和你的朋友,两个人一起玩 Nim 游戏: 桌子上有一堆石头。你们轮流进行自己的回合, 你作为先手 。每一回合,轮到的人拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。 假设你们每一步都是最优解。请编写一个函数…...
IAP固件升级分几步?(Qt上位机、)
前言 这周一直想做一个IAP固件升级的上位机,然后把升级流程全都搞懂 有纰漏请指出,转载请说明。 学习交流请发邮件 1280253714qq.com IAP原理 IAP的原理我就不多赘述了,这里贴上几位大佬的文章 STM32CubeIDE IAP原理讲解,及U…...
Otter改造 增加springboot模块和HTTP调用功能
环境搭建 & 打包 环境搭建: 进入 $otter_home/lib 目录执行:bash install.sh 打包: 进入$otter_home目录执行:mvn clean install -Dmaven.test.skip -Denvrelease发布包位置:$otter_home/target 项目背景 阿里…...
Vue.js vs React:哪一个更适合你的项目?
🌷🍁 博主猫头虎(🐅🐾)带您 Go to New World✨🍁 🦄 博客首页——🐅🐾猫头虎的博客🎐 🐳 《面试题大全专栏》 🦕 文章图文…...
Debian环境下搭建STM32开发环境
1. 安装交叉编译工具,解压gcc-arm-none-eabi-10.3-2021.10-x86_64-linux.tar.bz2,并且把交叉编译环境添加到path路径。 2.安装下载工具驱动和下载工具 # 安装下载工具openocd sudo apt -y install openocd 3.下载测试 sudo openocd -f cmsis-dap.cfg -…...
如何防止商业秘密泄露(洞察眼MIT系统商业机密防泄密解决方案)
在当今的商业环境中,保护公司的商业秘密是至关重要的。商业秘密可能包括独特的业务流程、客户列表、研发成果、市场策略等,这些都是公司的核心竞争力。一旦这些信息被泄露,可能会对公司的生存和发展产生重大影响。本文将探讨如何通过使用洞察…...
题目 1062: 二级C语言-公约公倍
输入两个正整数m和n,求其最大公约数和最小公倍数。样例输入 2 3样例输出 1 6 这题一知半解的, 最小公倍数两数の积/最大公约数; 最大公约数通过迭代法求得(见其下), 作为a,b两数有一个属为有一个为0为无效数据时 《-----a%b等…...
【Leetcode】148.排序链表
一、题目 1、题目描述 给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。 示例1: 输入:head = [4,2,1,3] 输出:[1,2,3,4]示例2: 输入:head = [-1,5,3,4,0] 输出:[-1,0,3,4,5]示例3: 输入:head = [] 输出:[]提示: 链表中节点的数目在范围 [0, 5 …...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...
全面解析数据库:从基础概念到前沿应用
在数字化时代,数据已成为企业和社会发展的核心资产,而数据库作为存储、管理和处理数据的关键工具,在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理,到社交网络的用户数据存储,再到金融行业的交易记录处理&a…...
