第4次课-UML介绍 【00：02：00】 统一建模语言，所有人都遵守它，比如它的形状代表什么意思，是大家共知的。 当你说明系统来做什么的，最初是厚厚的文档，不利于分析，漫漫给出了一个建模语言。基于了面向对象的思想。 想想UML为什么是这样子，它可以描述什么东西，和我们的系统有什么关系？ 需求定义清楚是非常重要的。 对于一门课 不一定需要有深刻的理解，可以对其他学科有一些理解。 用例也是模型（老师说的）。 2021-03-18 系统建模 ustc 系统建模
第7次课 【04：40】开始上课 需求分析概览 【20：28】requirement analysis-taxonomy 【25：50】系统动态的行为 【41：10】bahaviour primitives:actions and activities 【55:20】Events,Transitions,伪状态 。。。 【01：10：50】Submachines,Entry,and Exit Poin 2021-03-18 系统建模 ustc 系统建模
Untitled 第13次课平摊分析 合计法分析1.栈操作的例子因为三个操作不是相互独立的，一个对象入栈后最多弹出一次 ==>在非空栈上完成的pop次数(包括multipop操作)最多为push的次数 又因为初始栈为空，且n个操作中push的次数<=n ==>pop次数<=n ==>n次操作在最坏情况下的总时间<=2n = O(n) ==>每个操作的平摊时间(平均代价)为T 2021-03-18 期末 ustc 算法导论笔记 期末
算法导论2020期末背诵版 一、 数据结构1、 红黑树、序统计树、区间树1) 红黑树的性质、操作及时间 2) 红黑树的应用——序统计树、区间树的定义、构造 3) 数据结构的扩张步骤 1.1红黑树 红黑树的性质（P163）：(背) 1、每个结点要么是红的要么是黑的。 2、根结点是黑的。 3、每个叶结点（叶结点即指 NIL 或 NULL 结点）都是黑的。 4、如果一个结点是红的，那么它的两个儿子都是黑的。 5、 对于任意结点而 2021-03-18 期末 ustc 算法导论笔记 期末
最后一次课 一、判断 选择 20-30分 送分 二、综合题 50-60分 简答 画图 红黑树 求最大流 算法分析：递归算法的时间分析 平摊分析 阅读算法 回答问题 比如哈夫曼编码 怎么得到一颗最优的前缀码树 三、算法设计20-30分 1-2个题。 红黑树 的插入 删除一个结点 不考。 插入删除算法的时间复杂度要清楚。 不会有这样的题：用胚的方法来求最优解。 但要明白胚的定义和基本概念 怎么证明问题 2021-03-18 期末 ustc 算法导论笔记 期末
第4次课 master方法的特殊不适用情况 快速排序算法分析 (分治) 快排将原始数组分为4个区域，往后移动的方法不好 交换的方法好 交换的方法patition的T（n）为什么是O(n)? 交换的方法的整体时间复杂度分析：三种情况 最坏情况 用递归树方法分析，为什么是🌲的高度越大，层数越高，时间复杂度越大？55min 最好情况 子问题的规模一样大时 为什么用<=号：放大了规模 平均情况 2021-03-18 算法导论笔记 ustc 算法导论笔记
第6次课-红黑树与区间树 动态操作中主要的是插入和删除一个结点。 相对于删除操作来讲，插入一个结点还是比较简单。 插入分成两步： ①首先按二叉查找树查找一个结点(保证二叉查找树的性质) ②对遭到破坏的红黑树的特性进行恢复fixup 调整原则： ①不能让树的高度变得越来越高 ②尽可能让处理的情况越少越好 rb-delete中的tree-delete和二叉查找树的tree-delete的一点不同 2021-03-18 算法导论笔记 ustc 算法导论笔记
第9次课-LCS 2020-05-18 cut and paste 反证 证明最优子结构性质 26：00 step243:20 最优二叉查找树 虚拟关键字。 根节点深度为0 最大的关键字的结点挑出来当做根，他不是最优的 01：24：00 证明最优二叉树的最优子结构性质01：43:00 贪心思想 第二节视频 活动选择问题 2021-03-18 算法导论笔记 ustc 算法导论笔记
算法导论实验一 实验一 用分治法求解数组的中位数和最大子集题目一：寻找两个有序数组的中位数 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序 数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。 示例 1: nums1 = [1, nums1 = [1, 3] nums2 = [2] 则中 2021-03-18 算法导论笔记 ustc 算法导论笔记
算法导论实验二 实验二 典型排序算法训练：快速排序、计数排序一、快速排序1. 算法原理 快速排序的思想是任找一个元素作为基准，对待排数组进行分组，使基准元 素左边的数据比基准数据要小，右边的数据比基准数据要大，这样基准元素就放 在了正确的位置上。然后对基准元素左边和右边的组进行相同的操作，最后将数 据排序完成。 2. 流程图 3. 正确性分析 1）初始：i=p-1，j=p，p 与 i 之 2021-03-18 算法导论笔记 ustc 算法导论笔记
3.1 渐进记号 主要使用渐进记号来描述算法的运行时间 渐进记号实际上应用于函数 ΘΩΟ Θ记号 $Θ(g(n))$表示函数集合 若存在正常数$c_1$和$c_2$，使得对于足够大的自然数$ n$ , 函数$f(n)$ 能夹入$c_1g(n)$ 与 $c_2g(n)$ 之间，则$f(n)$ 属于集合$Θ(g(n))$，可以记做$f(n)\inΘ(g(n))$ ，通常记 $f(n)=Θ(g(n))$ ，但 2021-03-18 算法导论笔记 ustc 算法导论笔记
实验五 实验五：0-1 背包问题的算法设计学号:SA19225157 一、实验要求算法设计： 输入物品数 n，背包容量 c，输入 n 个物品的重量、价值，在以上算法中任选两个实现 最优解决 0-1 背包问题。 请问：所选算法的实现流程图或者伪代码是什么？比较时间复杂度和空间复杂度，得出 什么结论？ 1.动态规划方法算法的实现代码语言：Java public void dongtaiguihuapublic 2021-03-18 算法导论笔记 ustc 算法导论笔记