启用 Linux 环境 这里使用的是 WSL（Windows Subsystem Linux）环境，环境配置参考这里 Linux 安装 Emscripten Download and install 安装 python3 sudo apt install python3 安装 git sudo apt install git 创建目录并 clone emsdk sudo git clone https://github.com/emscripten-core/emsdk.git 更新 emsdk 并激活 cd emsdk git pull # Download and install the latest SDK tools. ./emsdk install latest # Make the "latest" SDK "active" for the current user. (writes .emscripten file) ....
一、暴力算法 $\mathcal{O}(n^3)$ 遍历数组的所有子数组集合，并对其求和，筛选出和的最大值 int maxSumOfSub1(int* array, int length){ int maxSum = 0; int startIndex = 0, endIndex = 0; for(int i = 0; i < length; i++){ for(int j = i; j < length; j++){ int sum = 0; for(int k = i; k <= j; k++) sum += array[k]; if(maxSum < sum){ maxSum = sum; startIndex = i; endIndex = j; } } } cout << "Begin:" << startIndex << " End:" << endIndex << " Num:" << maxSum << endl; return maxSum; } 二、前缀和 $\mathcal{O}(n^2)$ 先把数组的前 i 项和求出来并将其保存到数组中，然后计算所有子数组集合的和，筛选其中最大的...
线性结构 二元组 B = (K, R) , K = {a0, a1, …, an-1 }, R = {r}，其中 r 为前驱后继关系，具有反对称性和传递性 唯一的开始结点（表头）：没有前驱，只有一个唯一的后继 唯一的终止结点（表尾）：没有后继，只有一个唯一的前驱 内部结点：一个唯一的前驱和一个唯一的后继 线性表 线性表简称表，是零个或多个元素的有穷序列 表目：线性表中的元素 文件：含有大量记录的线性表又称为文件 索引（下标） 表的长度 空表：长度为零的线性表(n=0) 线性表分类 按访问方式划分： 直接访问型 顺序访问型 目录索引型 按存储方式： 顺序表（数组） 链表 按操作： 线性表：不限操作 栈：在同一端操作，在深度优先搜索、递归等算法中有很好的应用 队列：在两端操作，在宽度优先搜索、层次化处理中有很好的应用 顺序表 顺序表俗称向量，是用数组实现的（固定长度的一维数组） 按索引值从小到大存放在一片相邻的连续区域 结构紧凑，存储密度为1（存储密度 = 数据本身所占存储 / 整个数据结构所占存储） 物理存储关系就能表示逻辑关联关系 链表 链表需要指针表示逻辑关联关系，存储效率不如顺序表 有头链表和无头链表 在一些边界处理的时候，要注意头结点（head）和尾结点（tail）的特殊处理 讨论 线性表的分类方法有哪些？各种线性表名称中，哪些跟存储结构相关？哪些跟运算相关？...
算法的时间和空间性能非常重要 一、算法的渐近分析 当 n 增大到一定值后，其他的常数项和低幂次项都可以忽略，只需确定是在什么量级（线性、n 方、指数级等） 1. 大 $\mathcal{O}$ 表式法 函数增长率上限 2. 大 $\Omega$ 表式法 函数增值率的下限 3. 大 $\Theta$ 表示法 当上、下限相同时则可用 $\Theta$ 表示法 二、增长率曲线 三、数据结构和算法的选择 仔细分析所要解决的问题 特别是求解问题所涉及的数据类型和数据间逻辑关系（问题抽象、数据抽象） 数据结构的初步设计往往先于算法设计 注意数据结构的可扩展性 考虑当输入数据的规模发生改变时，数据结构是否能够适应求解问题的演变和扩展 三、思考题 数据结构的三个要素任何一个发生改变，都是不同的数据结构，请举例讨论 双向链表和二叉树的存储结构其实是一样的，他们的不同在于逻辑结构。 数组和向量都是线性表，其存储形式不同，成为不同的数据结构。 算法设计目标是什么？ 时间和空间的权衡 易读 易编码 易调试 易维护 易扩展 算法选择的过程？ 要求在时间复杂度 $\mathcal{O}(n)$、空间复杂度 $\mathcal{O}(1)$，使数组元素循环向右移动 K 位
一、问题——算法——程序 问题：一个函数，从输入到输出在一种映射 算法：对特定问题求解过程的描述，是指令的有限序列 程序：算法在计算机程序设计语言中的具体实现 二、算法的特性 通用性：参数化的，能对一类问题进行参数化输入并问题求解 有效性：有限条有效指令组成的指令序列，保证计算结果的正确性 确定性：算法的下一步执行步骤必须明确 有穷性：执行必须在有限步内结束，不能有死循环 三、基本算法分类 穷举法： 遍历每一个元素，比较低效，但是是一种万能的算法；对于一个问题，如果一时想不出好的算法的话，可对小规模数据采用穷举法剖析问题的特性和数据的特性，进而寻求更高效的算法 回溯、搜索： 能进则进，不能进则换，不能换则退，如树和图的遍历 递归分治： 二分查找，以及快速排序、归并排序，都是经典的分治算法思想 贪心法： 其数据具有贪心性质，每次求解的时候都采用当前的最佳解，最终得到最优解，如 Huffman 编码树、最短路径 Dijkstra 算法、最小生成树 Prim 算法 动态规划： 得到小规模问题的最优解，然后在更大规模的时候去组合这些最优解，最后得到全局的最优解，如图的两两结点之间最短路 Floyd 算法。要求具有最优子结构性质以及无后效性，动态规划的子结构有重叠，而递归分治子结构不重叠。 四、“监视哨”顺序检索 设置“监视哨”后，在查找过程中不用判断 i 是否越界，少一次判断，算法的运行效率会更高