第16次课-二项堆的操作和Fieb堆

【06：00-17：30】开始上课 复习上次看的内容。 插入一个结点不能插入到二项树中，因为插入后不满足二项树的性质。 【17：30】 【43：00】减操作【52：00】删除任意结点 【01：02：30】FIb堆 【01：23：50】FIB堆的逻辑表示 mark非常重要 看算法实现时 要重点看。 刚创建结点时，他的mark属性为假。 fai0 表示空堆。 二项堆结点度的上届为l

算法导论笔记
ustc 算法导论笔记

第3次课

[TOC] 递归形式的时间函数T(n)的解法递推法 低阶项忽略不写，因为对增长速率没什么影响 Θ(1)和C是等价的,Θ(n)和cn是等价的 为什么令n = 2的i次方? 不等于时，结果一样 更清晰的方法：递归树方法 更加复杂的问题也可以用递归树方法 没搞清楚？ cn在这里是低阶项 大部分算法都有基本步骤 Fib数包含重叠子问题，不适合分治法，可以考

算法导论笔记
ustc 算法导论笔记

第5次课-红黑树

红黑树首先是一颗二叉查找树。 二叉树删除结点的原则： ①删除操作应简单②删除不应使得树的高度增加③要处理的情况少（③属于红黑树） 二叉树删除过程中的3个指针 z:被删除结点 y:被删除结点Z的中序后继,也叫实际被删结点。此种情况下Z的左右孩子都存在 x:y的孩子，也叫拼接指针 二叉查找树的很多操作的时间复杂度跟树的高度有关 二叉查找树的高度可能为N,退化为单链表 二叉查找

算法导论笔记
ustc 算法导论笔记

第8次课-动态规划

用动态规划求解问题 和分治法是类似的。 首先要减少问题的规模。 分治法的问题：自顶向下会对子问题进行重复计算,时间复杂度会达到指数级. 但是动态规划是从自底向上，为了避免重复计算，采用查表(数组)的方式。 矩阵链乘的最优子结构的性质的表现形式和装配线调度是不一样的，要复杂一些。 1-n有n-1种。 最优子结构：问题分解后所有子问题的解都是最优的 上面就是递归式 底是什么？ 实际上在实

算法导论笔记
ustc 算法导论笔记

实验四

实验四 贪心算法实现最佳任务调度实验[学号 : SA19225157] 一、实验内容实现一个任务调度问题：在单处理器上具有期限和惩罚的单位时间任务调度 实现这个问题的贪心算法，并写出流程图或者伪代码。 将每个 Wi 替换为 max{W1,W2……Wn}-Wi 运行算法、比较并分析结果。 二、算法思路及代码 按通用的加权胚的贪心算法，把任务先按权值递减排列 结果集A一开始是空集，是独立

算法导论笔记
ustc 算法导论笔记

第13次课-平摊分析

【27：50】平摊分析开始 平均情况下时间复杂度通常需要借助统计概率分析(比较麻烦)[基本/传统的分析方法 ] Tarjan提出了平摊分析 T(n) 是调用的次数，而不是输入的规模、 实际上将n等同于输入的规模 【52：45】开始先用传统分析法分析连续n个操作 n个multipop为什么是O(n^2^) 传统方法不考虑各操作的关联性，就是这么考虑的，平摊分析要考虑 也就是②

算法导论笔记
ustc 算法导论笔记

第2次课-渐进法与分治法和递归

[TOC] 不同算法循环不变式不同 什么叫循环不变式？ 第二章 渐进符号2.1 等号的意思是说2边的函数增长速率相同，而不是绝对值相等 2.2 O符号 紧上界：对于例4，n是f(n)的上届，找不到比n更小的f(n)的上届松上界：对于例5,实际上f(n)的上界没那么大，还可以小o符号只能表示松上界 2.3 符号 第一个符号等式两边的函数可以交换，第二个第三

算法导论笔记
ustc 算法导论笔记

第7次课-动态规划

区间树及动态规划 定理14.2 循环不变式证明 查找算法的正确性 动态规划 分治法中：分解的子问题 大量重叠时，此时分治法效率不高。 Programming 其实不是编程，是查表。 最优解可以是不唯一的，是一个集合 最优解值是唯一的，是边数，在求最短路径举例中 递归是从上往下计算，因此会产生很多重复计算 第1步是最关键的，也是最困难的。 动态规划的方法本质上是一种查表的方法

算法导论笔记
ustc 算法导论笔记