- ——————————————————基础—————————————————
- 常见的数据结构可以分成哪几类？
- 数据的存储结构有哪几种？
- 什么是算法？算法应具有哪些特性？
- 时空复杂度判断
- 时间复杂度
- 空间复杂度
- ——————————————————线性表————————————————
- ——————————————————树——————————————————
- 遍历
- 非二叉树转化为二叉树
- 哈夫曼树（最优二叉树）
- 搜索二叉树
- 平衡二叉树
- ——————————————————图——————————————————
- Dijkstra算法
- 关键路径
- 最小生成树
- Prim算法
- Kruskal算法
- 二叉查找树
- ——————————————————排序—————————————————
- 冒泡排序
- 选择排序
- 插入排序
- 快速排序
- 归并排序
- 堆排序
- ——————————————————算法思想———————————————
- 贪心（Dijkstra在上边）
- 区间选点
- 活动安排
- DP
- 三角dp
- 最长公共子序列
- 加分二叉树
- 01背包
- 分治
- ——————————————————散列表————————————————
本文章不涉及任何代码。 ——————————————————基础————————————————— 常见的数据结构可以分成哪几类？
一、根据逻辑结构（数据元素之间的关系）
①线性结构：数据元素一对一的关系
②树型结构：数据元素一对多的关系
③图形结构：数据元素多对多的关系
④集合结构：集合结构中的数据元素除了属于同一个集合外，它们之间没有其他关系。各个数据元素是“平等”的，它们的共同属性是“同属于同一个集合”。
二、根据存储结构（数据的逻辑结构在计算机中的储存形式）
①顺序存储：把数据元素放在地址连续的存储单元里，其数据的逻辑关系和物理关系是一致的。
②链式存储：数据元素的存储关系不能反应其的逻辑关系，即逻辑关系和存储地址不一定对应。
- 总结：逻辑结构是面向问题，而存储结构是面向计算机的。
根据以上两点具体数据结构有：数组、栈、链表、图、散列表、队列、树、堆。
数据的存储结构，即数据在计算机中的存储形式。
一、顺序存储
- 在一块连续的地址中一个接一个的存储数据，
二、链式存储
- 逻辑位置与物理位置不相统一，通过指针来指定逻辑关系。
三、索引存储
- 采用附加索引表的形式来存储结点，类似一种固定长度的链表。
四、散列存储
- 根据结点的关键字直接计算出该结点的存储地址的一种存储结构。
算法的定义：对特定问题求解步骤的一种描述，是指令的有限队列。其中每一条指令表示一个或多个 *** 作。
算法的特性：
一、有穷性：
- 一个算法必须在有穷步内完成，即必须要在一个可预见的时间完成。
二、确定性：
- 算法的每一步必须有明确的定义，即不能有二义性的存在。在同一个算法中对于相同的输入所产生的输出将会是相同的。
三、可行性：
- 算法中的每一步都可以通过有限次执行已经实现的基本运算得以实现。
四、输入：
- 一个算法具有零个或多个输入，这些输入取自特定的数据对象集合。
五、输出：
- 一个算法具有一个或多个输出，这些输出同输入之间存在每种特定的关系。
- 由数据范围反推算法复杂度以及算法内容
来源：由数据范围反推算法复杂度以及算法内容
n
≤
1000000
=
>
O
(
n
)
n≤1000000 => O(n)
n≤1000000=>O(n), 以及常数较小的 O(nlogn)O(nlogn) 算法 => 单调队列、 hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 O(nlogn)O(nlogn) 的做法：sort、树状数组、heap、dijkstra、spfa
n
≤
10000000
=
>
O
(
n
)
n≤10000000 => O(n)
n≤10000000=>O(n)，双指针扫描、kmp、AC自动机、线性筛素数
n
≤
109
n
≤
109
=
>
O
(
n
)
n≤109n≤109 => O(n)
n≤109n≤109=>O(n)，判断质数
n
≤
1018
n
≤
1018
=
>
O
(
l
o
g
n
)
n≤1018n≤1018 => O(logn)
n≤1018n≤1018=>O(logn)，最大公约数，快速幂，数位DP
n
≤
101000
n
≤
101000
=
>
O
(
(
l
o
g
n
)
2
)
n≤101000n≤101000 => O((logn)2)
n≤101000n≤101000=>O((logn)2)，高精度加减乘除
n
≤
10100000
=
>
O
(
l
o
g
k
×
l
o
g
l
o
g
k
)
n≤10100000 => O(logk×loglogk)
n≤10100000=>O(logk×loglogk)，k表示位数O(logk×loglogk)，k表示位数，高精度加减、FFT/NTT
——————————————————线性表————————————————
——————————————————树—————————————————— 遍历
先序遍历：①访问根节点；②访问当前节点的左子树；③若当前节点无左子树，则访问当前节点的右子树；
中序遍历：①访问当前节点的左子树；②访问根节点；③访问当前节点的右子树；
后序遍历：从根节点出发，依次遍历各节点的左右子树，直到当前节点左右子树遍历完成后，才访问该节点元素。
例题：（以之两种遍历序列求原树以及第三种遍历序列）
流程：加线，去线。同一父节点的子树只保留最左子树。
例题：
前置知识：
- 路径：在树中，一个结点到另一个结点之间的通路，称为路径。
- 路径长度：在一条路径中，每经过一个结点，路径长度加 1 。
- 结点的权：给每一个结点赋予数值，被称为这个结点的权。
- 结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。
算法解释：
用 n 个有权值的结点构建一棵二叉树（结点全为叶子），若构建的树带权路径长度最小，则称这棵树为最优二叉树或者哈夫曼树。
权重越大的结点离树根越近。
例题：
例题：
搜索二叉树 平衡二叉树 ——————————————————图—————————————————— Dijkstra算法解释：
从给定点开始。查找该结点到其余结点的距离（根据已知边更行）。每次选择一个最短的路。
证明正确性：基于贪心思想。
假设所选边D1不是最短的，则一定还存在一个更短的D2，使D2
D2=d2+k。
从选择策略来看d2>d1。所以D2>D1（不存在负数）。与假设冲突。
例题：
解释：从一点开始，每次选择能选择的边最小的边，直到形成连通图（n-1）。
例题：和Kruskal的例题相同。
Kruskal算法解释：每次选择最小权重的边，选择后判断是否成环（并查集）。成环则跳过这条边，直到形成连通图（n-1）。
例题：
解释：
第一个元素为根节点。每加入一个元素从根节点开始判断，当小于当前结点向该结点的左子树移动判断，大于则向右子树。
删除一个结点则向左子树找个最大值，或右子树最小值。
例题：
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)，可以简化当一次循环没有发生改变的时候就退出。
解释：通过两两比较关键字，得出升序序列或者降序序列。每次比较都将最大或最小的放到最后。
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
解释：在未排序序列中找到最小（大）元素，与已排序的后一个元素交换，然后再从剩余未排序元素中继续寻找最小（大）元素。
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
解释：规定第一位元素为有序，取出下一位元素对已经有序的范围进行比较插入
时间复杂度：最坏 O ( n 2 ) O(n^2) O(n2)，平均 O ( n l o g n ) O(nlogn) O(nlogn)
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）