Blog

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）。 出入栈以及判断空栈操 阅读更多…

中位数：分为上中位数和下中位数，上中位数即长度除2向上取整，下中位数为长度除2向下取整。一般说中位数默认下中位数。 顺序统计量：即第几小的数。一个数组的第一顺序统计量即为最小的数，第n顺序统计量即为最 阅读更多…

1 计数排序 计数排序假设n和输入元素中的每一个都是在0到k区间内的一个整数，其中k为某个整数。当k=O(n)时，排序的运行时间为Theta(n)。 计数排序的思想是每输入一个元素x，确定小于x的个数 阅读更多…