数据结构与算法学习笔记

java一.数据结构简介1. 为什么要有数据结构数据太多、太乱 → 无法高效处理 →必须结构化2. 数据结构的两大分类逻辑结构数据之间的关系怎么理解物理结构内存中的存储方式怎么实现3. 逻辑结构4 种本质 2 类)线性结构一对一线性表,栈,队列非线性结构一对多 / 多对多图多对多,树一对多4. 物理结构2 种顺序存储连续内存数组链式存储不连续靠指针链表一句话闭环数据乱 → 要结构 → 逻辑关系、物理存储。逻辑线性 / 非线性物理顺序 / 链式。二.算法简介1. 什么是算法算法 解决问题的一套 “有限、确定、可执行” 的步骤有输入、有输出、一定能结束不是无限循环2. 为什么要评价算法逻辑起点同一个问题可以有很多种算法但有的快、有的慢、有的占内存多、有的占内存少 →必须有标准判断好坏3. 算法的两个核心要求要求 1运行时间少越快越好要求 2占用内存少越省越好4. 两个要求 → 衍生出两个复杂度量化标准对应 “时间少” →时间复杂度衡量快慢对应 “内存少” →空间复杂度衡量占用5. 复杂度的统一逻辑为什么都看增长趋势时间、空间复杂度本质都是随数据规模变大消耗的增长趋势→ 只看最高次项忽略常数、低次项二.算法分析1.时间复杂度(1)为什么要分析时间复杂度算法要运行得快→ 需量化 “快慢” → 用执行时间衡量但直接测时间不准 → 转为统计执行次数执行次数 ≈ 执行时间步骤越多耗时越长(2)分析方法事前 vs 事后事后分析法运行代码实测实际耗时 不建议受机器、语言、数据影响结果不可靠无法预测大数据表现事前分析法不运行代码数学推导执行次数采用通用、稳定能预测大数据趋势是算法设计核心方法(3)事前分析的核心大 O 记法是什么描述执行次数随数据规模 n 的增长趋势的数学表示法只看量级不看精确值怎么记保留最高次项忽略常数、低次项、系数例T (n)2n²3n1 → 保留 n² → 记为 O (n²)(4)事前分析的规则可忽略加法常数、低次项、最高次项系数为什么忽略算法关注大数据下的表现常数只影响起步快慢不改变增长趋势低次项增长速度远低于最高次项n 足够大时可忽略不计系数仅为倍数不改变算法的增长级别不可忽略最高次项决定算法是快是崩是增长趋势的核心(5)常见大 O 阶常数阶 O (1)无循环、固定步骤与 n 无关增长最慢对数阶 O (log n)二分查找增长极慢线性阶 O (n)单层循环线性增长线性对数阶 O (n log n)高效排序归并 / 快速平方阶 O (n²)双层嵌套循环增长快立方阶 O (n³)三层嵌套循环增长极快排序从小到大O(1) O(log n) O(n) O(n log n) O(n²) O(n³)一句话闭环全链路关联要衡量算法快慢 → 用执行次数替代执行时间 → 分事前 / 事后分析 → 事后不准 → 用事前推导 → 事前用大 O 记法看趋势、忽略常数 / 低次项 / 系数因不影响大数据表现 → 常见复杂度按增长速度排序含常数阶 O (1)2.空间复杂度1. 前置知识位与字节为什么计算机只识别 0/1最小单位是位1 位存不下信息8 位打包为字节1 字节 8 位均为 2 的指数二进制天然翻倍硬件效率最高。Java 常见类型字节数byte (1)存小整数省空间short (2)比 byte 范围大折中int (4)最常用满足日常计算long (8)存超大整数float (4)单精度小数省空间double (8)默认浮点精度高char (2)Unicode 编码存全球字符boolean (1)仅存 true/false最小空间\对象 16 字节开销为什么对象需虚拟机管理存对象头构成标记字8 字节存哈希、锁状态 类型指针8 字节指向类16 字节原因64 位指针占 8 字节满足 8 字节对齐内存填充含原因为什么64 位 CPU 一次读 8 字节数据需对齐到 8 字节地址规则不足 8 字节自动填充避免跨块读取提升效率2. 空间复杂度自身空间复杂度的作用衡量算法内存占用多少。避免内存溢出OOM。优化空间适配低内存设备。空间复杂度是什么定义算法执行时额外占用内存空间随数据规模 n 的增长趋势。核心只算 “自己新开的空间”输入 / 输出不算。与时间复杂度大 O的相似之处都用大 O 记法只看增长趋势。都忽略常数、低次项、系数保留最高次项。都用于事前分析不依赖机器环境空间复杂度常用吗非常常用是算法评价的第二核心指标。面试必考尤其原地算法 O (1)。递归、动态规划、数组必须算空间。内存有限时空间比时间更关键。一句话闭环二进制→位 / 字节→类型按用途分配字节→对象头 16 字节管理→8 字节对齐填充→空间复杂度 额外内存增长趋势→同时间复杂度用大 O、看趋势→常用、防溢出、优化内存。三.排序算法1.冒泡排序1. 冒泡排序的目的对一组无序的整数序列通过相邻元素比较交换实现从小到大或从大到小的有序排列。2. 核心思想每一轮遍历比较相邻两个元素按规则交换位置,已排序元素不进入第二轮从小到大大元素逐步后移像气泡上浮到末尾从大到小小元素逐步后移像气泡上浮到末尾每轮确定 1 个最终位置重复 n-1 轮完成排序3.代码实现三种代码实现4.时间复杂度分析过程5.应用与拓展与讲解2.选择排序1.简介2.3.插入排序4.希尔排序5.归并排序6.快速排序7.综合分析四,线性表