• 高级算法复习


    时间代价

    主定理

    在这里插入图片描述
    在这里插入图片描述

    递归树

    排序

    在这里插入图片描述

    贪心算法

    • 贪心选择性(Greedy-choice property):
      通过做出局部最优(贪婪)选择,可以得出全局最优解——这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别

    • 最优子结构性质(Optimal substructure property):
      当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质——最优子结构性质是该问题可用 动态规划算法 or 贪心算法 求解的关键特征

    英语:全局最优解optimum solution
    与动态规划区别:是否产生最优解;贪心选择更简单高效;对应问题都具有最优子结构,但贪心算法要满足贪心选择性,动态规划满足重合子问题(overlapping subproblem)

    动态规划

    矩阵链乘法(Matrix-chain Multiplication)

    最长公共子序列(Longest Common Subsequence)

    凸多边形的三角形分解(Triangle Decomposition of Convex Polygon)

    最优二叉搜索树(The Optimal Binary Search Trees)

    B树

    • B树=B-树
    • B树的value在每个节点,B+树的value在叶子节点(内部节点只有key),2-3-4树是4阶B树(4 order)(子树个数可能有2,3,4个,也就是节点key可能有1,2,3个)
    • B树的最小度数(minimum degree)为t,代表每个节点最少有t个子树(根节点除外,根节点可以只有2个子树),即有t-1个key;并且每个节点最多有2t个子树,即有2t个key。题目中介绍B树会说:a B-tree with minimum degree 2
    • B树的阶数(order)=节点子树的上限,B树节点的最小度数t=这棵树的阶数为2t(4阶B树最多有4个子树,节点最小度为2)
    • B树节点的分裂:B树最小度为t,当节点有2t-1个key时也就是full时,如果进行分裂,则左子树有t-1个,右子树有t-1个key,把中间剩下的key移到上一层
    • B树的插入:直接按大小顺序插入到底层,往下走的过程中碰到full节点就分裂(这就避免了最底层节点分裂造成的网上连续分裂),走到底层碰到full节点就先分裂再插入

    红黑树

    五条性质

    在这里插入图片描述

    高,黑高,节点个数

    在这里插入图片描述
    黑高是高的一半: bh = h/2
    高为h的树的节点总数2h-1
    在这里插入图片描述

    红黑树插入节点

    1.父叔都是红
    在这里插入图片描述
    2.父红叔不红----一定接3
    在这里插入图片描述
    3.父红叔不红
    在这里插入图片描述

    哈希

    chain

    用链表解决哈希
    The expected time for an unsuccessful search for a record with a given key is = Θ(1 + α)。α是装载因子

    开放寻址法

    linear probing
    • Given an ordinary hash function h’(k), linear probing uses the hash function h(k,i) = (h’(k) +i) mod m.
    Quadratic probing
    • h(k,i) = (h’(k) +c1i+c2i2) mod m.
      Where h’(k) is an auxiliary hash function, c1 and c2 ≠0 are auxiliary constants.
    Double hashing
    • h(k,i) = (h1(k) +ih2(k)) mod m.

    证明要1/(1–α)个探针才能找到元素

    • Given an open-addressed hash table with load factor α= n/m< 1, the expected number of probes in an unsuccessful search is at most 1/(1–α).
  • 相关阅读:
    字节跳动大规模多云CDN管理与产品化实践
    【Python】使用Python库中的pymysql执行SQL
    主从复制的实现方案
    轻取软考45分之软考信息系统项目管理师范围管理​章节学习笔记
    数学建模(一):2022年国赛a题
    ​PNAS:alpha频率经颅电刺激调控大脑默认网络
    忆联SR-IOV解决方案:助力云数据中心节能提效,向“绿”而行
    GPT的历史
    《Linux设备驱动开发》第11章 内核内存管理
    随机函数变换示例
  • 原文地址:https://blog.csdn.net/double_yellow/article/details/134315211