【数据结构】sorting
前置概念说明稳定性排序算法的“稳定性”是指,如果两个元素有相等的键值,在排序后这两个元素的相对顺序应保持不变。换句话说,一个稳定的排序算法会保留输入数据中相等元素的相对顺序。
Q: 谁是不稳定的?
A;答曰:“快希选堆”
与其他技术的互动或对比
数据库: 在数据库查询中,稳定的排序算法能确保当你按多个字段排序时,每一级的排序都不会影响其他级别的排序结果。
搜索引擎: 稳定性在搜索结果排序中也很重要,以便维持其他相关因素(如页面权重)的原有顺序。
并行计算: 在并行计算环境下,稳定排序算法更易于实现,并且能更有效地维持数据的相对顺序。
机器学习: 在数据预处理阶段,使用稳定的排序算法可以防止模型因数据顺序改变而受到不必要的影响。
简而言之,稳定性是排序算法中一个经常被忽视但实际上非常重要的特性。它与其他计算领域有很多交集和应用
作者:Native8418
链接:https://www.zhihu.com/question/587663148/answer/3211983666来源:知乎
O(n^2) sorting algorithmsBubble SortSelection Sor ...
【数据结构】并查集
简介并查集是一种树形的数据结构,用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。
每个结点存储的是自己的父节点。
类型weighted-union存储权重信息:根节点存储的原本是-1,为了节省空间,可以把根节点存储的值乘上权重,例如权重为2的根节点,存储的值是-2;权重为3的根节点,存储的值是-3。
基本操作find1234567int find(int x){ if(x==parent[x]) return x; else return find(parent[x]);}
union1234567void union(int x,int y){ int fx=find(x); int fy=find(y); if(fx!=fy) parent[fx]=fy;}
其他union规则
按照高度
按照结点规模path compression 查找路径压缩路径压缩的本质是在查找返回的时候,将路径上的所有节点的父节点都指向根节点,这样可以减少后续查找的时间。
1 ...
【数据结构】图
基本概念
顶点(vertex)
边(edge)
有向图(directed graph)
无向图(undirected graph)
有向边(directed edge)
无向边(undirected edge)
顶点的度(degree)
入度(in-degree)
出度(out-degree)
路径(path)
简单路径(simple path)
环(cycle)
简单环(simple cycle)
连通图(connected graph):任意两个顶点之间都存在路径的无向图称为连通图。
连通分量(connected component)
强连通图(strongly connected graph):任意两个顶点之间都存在路径的有向图称为强连通图。
强连通分量(strongly connected component)
简单图与多重图:没有重复边和自环的图称为简单图,有重复边和自环的图称为多重图。
简单路径与简单回路:路径上的顶点不重复出现的路径称为简单路径。回路上的顶点不重复出现的回路称为简单回路。连通图、强连通图
若无向图中任意两个顶点之间都存在路径(不是边),则称该图为连通图,否 ...
【数据结构】优先队列和栈
优先队列的背景less flexibility, more speed
如果我们的目的是找到最小的值,比较其他数据结构:
Lists
If sorted: FindMin is O(1) but Insert is O(N)
If not sorted: Insert is O(1) but FindMin is O(N)
Balanced Binary Search Trees (BSTs)
Insert is O(log N) and FindMin is O(log N)
Hash Tables
Insert O(1) but no hope for FindMin
BSTs look good but…
BSTs are efficient for all Finds, not just FindMin
We only need FindMin
PQ 优先队列Useful if you want to keep track of the “smallest”, “largest”, “best” etc. seen so far.
1234567891011 ...
【数据结构】Btree家族
BtreeBtree 介绍
Btree 是一种多路搜索树,每个节点可以存储多个元素,每个元素可以有多个子节点。
对于一棵M阶的B树,每个节点最多有M个子节点,最少有⌈M/2⌉个子节点(⌈x⌉为向上取整符号);最多有M-1个元素,最少有⌈M/2⌉-1个元素。(B+树也是一样)
2-3树是一种特殊的 btree,2-3树的阶数为 3,每个节点最多有 2 个元素,最多有 3 个子节点。(其中“2-3”代表的是该树允许的子节点个数范围)
同样地,对于一棵4阶的2-3-4树,每个节点最多有4个子节点,最多有3个元素。每个节点最少有2个子节点,最少有1个元素。Btree 特性1.关键字集合分布在整颗树中;
2.任何一个关键字出现且只出现在一个结点中;
3.搜索有可能在非叶子结点结束;
4.其搜索性能等价于在关键字全集内做一次二分查找;
Btree 的插入
插入的时候,先找到插入的位置,然后插入到叶子节点中。
如果插入之后,叶子节点的元素个数大于 m,那么就需要进行分裂操作。
分裂操作:将叶子节点的元素分成两部分,左边的元素个数为 (m+1)/2,右边的元素个数为 m-(m+1)/2,然后将左边的 ...
【数据结构】AVL树+splay树
AVL树前置知识
二叉排序树:左子树的所有节点都小于根节点,右子树的所有节点都大于根节点
平衡二叉树:左右子树的高度差不超过1的二叉排序树
二叉树的高度:根节点到叶子节点的最长路径
二叉树的深度:根节点到叶子节点的最短路径
二叉树的平衡因子:左子树的高度减去右子树的高度
AVL树的定义
AVL树是一棵空树或者它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树的二叉排序树。
AVL树的调整
LL型单旋:右旋
RR型单旋:左旋
LR型双旋:先左旋再右旋
RL型双旋:先右旋再左旋
tips:旋转之后,根节点的平衡因子为0,左右子树的平衡因子为1或者-1
图解:AVL树的插入按照常规的二叉排序树的插入方法插入节点,然后从插入节点开始向上回溯,找到第一个平衡因子的绝对值大于1的节点,然后根据该节点的平衡因子和插入节点的值的大小关系,进行旋转操作。
AVL树的删除如果删除的节点是叶子节点,直接删除即可。如果删除的节点不是叶子节点,那么需要找到该节点的前驱或者后继节点来替换该节点,然后删除前驱或者后继节点。删除之后,从删除节点的父节点开始向上回溯,找到第一个平衡因子的 ...
【影评】《Oppenheimer》(奥本海默)
इदानीं अहं क्रूरः कटनकर्ता, जगतः नाशकः भवेयम्।
“我现在成了死神,世界的毁灭者。”
——《薄伽梵歌》
壹先说结论,个人觉得值得一看,无论是对冲着诺兰导演还是奥本海默传记或者是电影体验来的(看各人口味)。但是有点门槛:时长考验膀胱,音量考验耳膜,时间线考验理解。影片的剧情稍微了解二战历史或者是学过高中历史的应该都能看懂大概,但是如果对这块历史很有了解的应该看起来会更舒服。
电影的时长长达三个小时,虽然时间较长,但节奏紧凑。
影片基于真实历史背景,对于对物理学和二战历史政治感兴趣的观众来说将是一场盛宴。
剧情从中间开始,时间线分裂且跳跃,虽然不影响整体理解,但完全理解所有细节可能有一定难度。
演员阵容堪称豪华,演技也确实无可挑剔
人物和人名很多,再加上我有一点脸盲,看完一整部除了戏份特别多或者特别好认的角色,还有很多不知道哪里冒出来的名字/有印象叫不出名字的,但是不影响整体的理解。
全片无特效(除了为了引进大陆特殊处理过的桥段,那就挺明显的),全部实景搭建和拍摄。关于具体以及一些其他方面技术相关的消息,最近网上有很多采访诺兰的视频,可以 ...
计算机网络原理
b站中科大郑铨
课本:《自顶向下计算机网络》
第一章电路交换网络和分组交换网络
电路交换网络
电路交换不适合计算机之间的通信
连接建立时间长
计算机之间的通信有突发性,如果使用线路交换,则浪费的片较多
即使这个呼叫没有数据传递,其所占据的片也不能够被别的呼叫使用
可靠性不高?
TDM相对于FDM的优点
频谱效率:
更高的频谱利用率:TDM在时间上进行复用,不需要为每个信道分配不同的频段,避免了频谱资源的浪费,提高了频谱利用效率。
设备复杂度:
设备简单:TDM不需要复杂的滤波器来分离不同频段的信号,只需使用时间片分配即可,因此硬件实现相对简单。
减少干扰:
干扰更小:TDM信号在时间上是分离的,不存在不同频段之间的相互干扰问题,而FDM中不同信道之间的频谱相邻可能会产生干扰。
动态带宽分配:
灵活的带宽管理:TDM可以根据需要动态调整每个用户分配的时间片,便于管理和调整带宽分配,适应不同用户的需求。
同步和定时:
同步性强:TDM具有严格的时间同步要求,确保各个时隙的准确性,而FDM需要对不同频段进行同步和管理,复杂度更高。
电路交换网络 ...
编译原理实验
实验一:RE->NFA实验要点定义正则表达式规范定义NFA模型设计RE转NFA的过程解析正则表达式生成NFA任务1 实现正则表达式树构建算法 (实现类ParseRegex的parse()方法)main/java/org/qogir/compiler/grammar/regularGrammar/ParseRegex.java
任务2 Thompson Construction算法 (实现类ThompsonConstruction的translate方法)main/java/org/qogir/compiler/grammar/regularGrammar/ThompsonConstruction.java
任务3 处理错误的正则表达式