m路搜索树
m路搜索树定义一般定义:一棵 m 路搜索树, 它或者是一棵空树, 或者是满足如下性质的树:
根最多有 m 棵子树, 并具有如下的结构: 其中, 是指向子树的指针,; 是关键码,。
在子树 中所有的关键码都小于 ,且大于 ,。
在子树 中所有的关键码都大于
在子树 中的所有关键码都小于
子树 也是 路搜索树,
凸性(Convexity)
DefinitionA set is convex if for any , any , we have
How to judge whether a set is convexWay 1The first way is to use the Definition![[Convexity#Definition]]
Way 2The second way is that a set is convex if and only if the intersection intersection with an arbitrary line is convex. That is to say, if we let and let we would have which becomes a one-variable function. We could only consider the convexity of .
Note: The here represents the starting point of a line and the vector represents ...
锥(Cone)
Proper cone真锥是满足以下定义的锥
K is convex
K is closed
K is solid, which means it has nonempty interior
K is not pointed, which means that it contains no line ()We will used the Proper cone to define the generalized inequality.
Generalized inequalityDefine the generalized inequality with a proper cone is belowand define a strict partial order by
对偶锥(Dual cone)
Dual coneDefinitionDual cone of a given cone K is
Property
is convex even if is not.
if and only if is the normal of a hyperplane that support at the origin换句话说,只有当向量 是锥 的在顶点处的一个支撑超平面的法向量的时候,才会属于它的对偶锥,如图形象一些理解的话,就是想象一个原来的锥 ,然后对偶锥就是对两条边界射线做垂线,这两条垂线内部就是对偶锥。
implies
if has nonempty interior, then is pointed
Dual Generalized Inequalities![[Cone#Generalized inequality]] if and only if for all
Proof
Dual Characterization of Minimum Elementx is the minimum element of , with respect t ...
凸函数定义
定义 if convex if
定义域是凸的
满足 感性理解:任意的直线在函数上方
if strictly convex if
定义域是凸的
满足 和上面那个只差一个负号
特殊性质仿射函数既是凸函数,又是凹函数
基于导数的其它定义方式First-order condition如果函数 是可微的,那么函数 是凸的当且仅当
is convex
For all
Second-order condition如果 是二阶可微的,那么 是凸的当且仅当
的定义域是凸的
For all 这里的 是Hesson矩阵,考虑是不是正定的
判定方法0阶条件定义法:利用定义域中所有的直线和它相交![[image/Pasted image 20231109200631.png]]注意,这里的 中的 是任意一个
1阶条件![[image/Pasted image 20231109200748.png]]
2阶条件![[image/Pasted image 20231109200833.png]]
B 树
B树的的相关知识依赖m路搜索树:[[m路搜索树]]
定义一棵 m 阶B_树是一棵 m 路搜索树,它或者是空树,或者是满足下列性质的树:
根结点至少有 2 个子女
除根结点以外的所有结点 (不包括失败结点)至少有 个子女
所有的失败结点都位于同一层。Note: 失败结点:是当搜索值x不在树中时才能到达的结点注意:事实上,在B树的每个结点中还包含有一组指针D[m],指向实际对象的存放地址。K[i]与D[i] 形成一个索引项(K[i], D[i]),通过K[i]可找到某个对象的存储地址D[i]。
搜索时间分析B树的搜索时间分为两种情况考虑
搜索成功所需的时间:取决于关键码所在的层次
搜索不成功所需的时间:取决于树的高度。
插入节点的方法
B树是从空树起,逐个插入关键码而生成的
在B树,每个非失败结点的关键码个数都在之间。
插入在最底层的非失败结点开始。如果在关键码插入后结点中的关键码个数超出了上界 m-1,则结点需要“分裂”,否则可以直接插入
插入时节点分裂的方法设结点 p 中已经有 m-1 个关键码当再插入一个关键码后结点中的状态为 其中 , 这时必须把结点 p 分裂成两个结 ...
红黑树学习笔记
Definition
节点是红色或者黑色
根节点是红色
叶子节点是黑色
红色节点不能有红色子节点
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点(简称黑高)
ARB and RBARB(Almost red-black tree) 和红黑树的区别就是根节点是红色
Black heightThe black height of any or is well defined. which is the number of black nodes.
和B树的关系可以把同一层(两个红色节点链接在一个黑色节点后面记为一层)的红色节点和黑色节点放到一起,相当于就是一个2-4 B树
修复的基本操作红黑树的修复是通过变色、左旋和右旋三种操作组合而成的,关于旋转的操作详见[[AVL#AVL树基本结构]]
插入流程插入的概略过程:
先插入一个结点
将插入的结点标记为红色(Black height constraint仍然成立)
在保证Black height constraint的情况下,调整颜色和结构,使得Color constraint成立在插入节点之后,可能RBT的性质被破坏了 ...
let's encrypt申请证书命令
申请范域名证书命令使用certbot可以免费申请范域名证书。使用试输入下面的命令,注意替换命令为自己的域名。
1sudo certbot certonly -d "*.example.com" -d example.com -m YOUR_EMAIL --manual --preferred-challenges dns-01 --server https://acme-v02.api.letsencrypt.org/directory
申请单域名证书命令也可以申请单域名证书,命令如下
1sudo certbot certonly --manual -m YOUR_EMAIL -d example.com --preferred-challenges dns-01 --server https://acme-v02.api.letsencrypt.org/directory
Nginx的配置使用certbot申请的证书会保存在/etc/letsencrypt/live/example.com/下面,注意这里的是一个软连接,指向真正的证书
下面给出一个监听8080 ...
如何在本地搭建VSCode环境编写c++代码
文件结构在一个cpp项目中,文件结构如下:
12345678*|-- .vscode/| |-- setting.json| |-- launch.json| |-- tasks.json|-- bin/ |-- CMakeLists.txt|-- main.cpp
你需要修改的配置都在 .vscode/ 目录下面,在那里面修改对应配置
这里创建了一个 bin/ 目录用于存放临时生成的可执行文件
记得要先创建文件夹
tasks.json 内容示例tasks.json 用于指明编译、运行的配置,同样记得修改command为你自己的路径,并且把mingw的bin目录添加到path。并且记得在你的项目文件夹下面把 bin/ 目录创建好
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566{ "version": "2.0.0" ...
如何把hexo搭建的博客发布到自己的云服务器,包含部署https
本文将介绍如何把自己搭建的hexo发布到云服务器上
购买云服务器、域名以及ICP备案想要部署hexo博客,有一台具有公网ip的云服务器是必须的。
如果想要别人能够方便的访问你的博客,还需要申请一个域名。
如果你希望你的博客能够在大陆地区被正常访问,那么还需要进行ICP备案。
以上三者作为前置条件,本文不做赘述,请自行上网搜索相关教程。
在云服务器上配置好ssh公钥登录在你希望使用的账户的~目录下的.ssh文件夹中,创建authorized_keys文件,将你的公钥复制进去。注意公钥是一行一个。然后把这个文件的权限改为600。
1chmod 600 authorized_keys
这样就可以进行ssh公钥登录了。
可以尝试使用ssh命令登录一下,如果没叫你输密码,那么就可以进行下一步了。
安装Nginx和gitubuntu和debian系列执行
1sudo apt install nginx git
centos系列执行
12sudo rpm -ivh http://nginx.org/packages/centos/7/noarch/RPMS/nginx-release-centos- ...