Blog

单源最短路径：给定一个图，我们希望找到从定源节点s到每个结点v的最短路径。 松弛操作：本章的算法需要使用松弛技术，对于每一个点，我们多维护一个变量d，用来记录从源节点到结点v的最短路的权重上界（也就是 阅读更多…

最小生成树就是在一个图中找到一条树，这些树可以包括图中所有的点并且这些 边权重的代价是最低的。如下图： 在本章中，我们将讨论两个最小生成树的算法：克鲁斯卡尔（Kruskal）算法和普利姆（Prim）算 阅读更多…

1.图的表示 对于图G=(V,E)，我们可以用两种标准方法表示。一种是邻接链表，一种是邻接矩阵。 如下图分别就是图，图的邻接链表表示，图的邻接矩阵表示。 对于稠密图，我们一般使用邻接矩阵来表示，对于稀 阅读更多…

在摊还分析中，我们求数据结构的一个操作序列中所执行的所有操作的平均时间，来评价操作的代价。 1.聚合分析 利用聚合分析，我们证明对虽有n，一个n个操作的序列最快情况下花费总时间T(n)。因此在最坏情况 阅读更多…

求解最优化问题的算法通常需要经过一系列的步骤，在每个步骤都面临多种选择。对于许多最优化问题，使用动态规划算法来求解最优解问题有些杀鸡用牛刀了，可以使用更简单、更高效的算法，也就是贪心算法来解决这一问题 阅读更多…

动态规划（dynamic programming）与分值方法相似，都是通过组合子问题的解来求解原问题。 分治方法将问题划分为互不相交的子问题，递归地求解子问题，再将他们组合起来，求出原问题的解。 而动 阅读更多…

上一章的二叉搜索树（平均时间复杂度O(n)），很容易在n个长度下形成高度为n-1的一条链，为了避免这种情况，引入红黑树，红黑树是许多“平衡”搜索树中的一种，可以保证在最坏情况下基本动态集合操作时间复杂 阅读更多…

1.什么是二叉搜索树 二叉搜索树：对任何结点x，其左子树中的关键字最大不超过x.key，其右子树的关键字最小不低于x.key，不同的二叉搜索树可以代表同一组值的集合。 二叉搜索树的性质允许我们通过一个 阅读更多…

1.直接寻址表 直接寻址法类似于标记数组，假定有一组序列的最大值为n，定义一个长度为n的零数组，如果序列中有数i，则数组第i个元素为1。 2.散列表 散列表则通过一个函数，将序列中的元素进行某种函数运 阅读更多…

1.栈和队列 栈和队列都是动态集合，栈实现的是一种后进先出的策略，队列实现的是先进先出的策略。 栈 栈的insert操作称为压入（push），delete操作称为弹出（pop）。 出入栈以及判断空栈操 阅读更多…