数据结构绪论
本来不想再总结ds的 但是一想这个学的快 也不能框框学吧 所以就花点时间总结一下吧 是个好久跟第一遍相比确实快了很多 理解也更加深入 所以这个系列与其说408最后ds的总结 不如叫做ds的深入补充 会搭配一些综合题算法的扩展
啥是数据结构？相互之间存在一种或多种特定关系的数据元素的集合
所以太简单的概念不再过多阐述 参考之前即可
- 数据
- 数据元素：数据基本单位
- 数据项：数据元素最小单位
- 数据对象：具有相同性质的数据元素的集合
- 数据类型：一个值的集合及定义在该集合上的一组操作的总称
- ADT抽象数据类型：一个数学模型及定义在该模型上的一组操作
参考之前的图
所谓数据结构无非研究三个东西：
- 逻辑结构
- 物理(存储)结构
- 数据的运算
ds逻辑结构
逻辑结构和数据在计算机中的存储方式无关 独立于具体系统的
就XX的一句话 假的东西 用来描述的玩意
常见的逻辑关系
存储结构：在计算机中的具体实现 (数据元素的表示及相互关系的表示)
- 顺序存储
- 链式存储
- 索引存储
- 散列(哈希)存储
算法
对特定问题求解步骤的描述 一个有穷的指令序列
知道了数据结构关系 那么之间的运算就需要用到算法
实际上ds和算法紧密联系
当然在此推荐力扣算法题 活跃大脑应付一些考试场景 并非完全没用也不是完全绝对有用
https://leetcode.cn/studyplan/top-100-liked/
重要五个特性：
- 有穷性
- 确定性
- 可行性
- 0个/多个输入
- 1个/多个输出
评判算法的好坏：
- 正确性
- 可读性
- 健壮性
- 高效率和低存储消耗
那比如甩给你一个代码 这个算法怎么确定度量 就是具体的东西
- 时间复杂度
- 空间复杂度
用到上述两个东西 尤其是时间复杂度 也是本节考点所在
时间复杂度
一句话描述算法执行时间和问题规模n的正比关系
用语句频度即 T执行次数 来衡量
算法的设计会有时间复杂度的好坏
取最坏时间复杂度为算法效率的标准评价
大道至简 遵从两个准则
常见的时间复杂度排序
不着急做题 先看一下做这类题目的方式
- 1.t次数和条件代入情况
- 2.t次数和n变化情况
- 3.嵌套复杂加 分析累计算
没错较之前升级了 在题目中应用
注意这里的嵌套
对比之前为何会多出第三条 因为就是后面题的作用
简单的直接乘法规则用于内层循环固定的n 不依赖外层变量
对比几道真题
这道题目就需要分析 外层循环+内层循环算时间复杂度
我们好好来拆解这道题目
注：我这种方法包括之前总结的 其实根本就不是正确解题方式 而是我自创的容易理解的方式 所以可能有时就是错误的 但大部分题目可以歪打正着
这个在初始c语言函数肯定见的不见了
再次申明 我的这种做题方式不是正确的！ 而是我自己快速做题的一种方式 所以酌情参考 核心就是：
- 看执行次数t和n的变化 如果是t的平方 那时间复杂度就是O(根号n)
- 看执行次数t和条件的变化 如i*i<n 求出t和i的变化 代入 得到时间复杂度
- 其他参考加法准则取max 和(固定n)嵌套相乘时间复杂度
- 如果碰到复杂的嵌套 就要正常分析 看t的次数和时间了(这个其实才是正确的)
还是不懂我的方式？那最后看一道题目理解
第一种方式分析t和n的变化 就是执行一次 看看n得取几
其实这种很抽象 就是得到n对于t的规律 然后求出时间复杂度
但是这种方式大部分都能解决
第二种方式分析t和x的变化然后代入条件 得到关于t<n/2的关系 也能求出
因为这个多了一层分析 然后再代入 所以没有第一种快 但是按理说这种不容易出错
其实也类似正确解法
空间复杂度
一句话就看需不需要额外的存储空间
后续线性表一章我们会着重分析
大致总结到此 对比之前的总结 更为详细 也再理解书本更透彻