Blog

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

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

对于包含n个数的输入数组来说，快速排序是一种最快情况时间复杂度为O(n^2)的排序算法。虽然最坏情况时间复杂度很差，但是快速排序通常是实际排序应用中最好的选择，因为它的平均性能非常好，期望是O(nlg 阅读更多…

堆排序的时间复杂度为O(nlgn)，具有原址性。 同时需要区分“垃圾收集存储机制”中的堆，例如Java语言中的定义，这里的堆不是垃圾收集存储，只是一种数据结构。 1.堆 如下图是一个二叉堆： 二叉堆可 阅读更多…

1 雇佣问题 假如你要雇佣一名新的办公助理。你承诺在任何时候，都要找到最合适的人来担任这项任务，且只能有一个人被雇佣，当雇佣新的人时，之前的要解雇，同时还要支付给中介一大笔中介费。 我们假设面试的费用 阅读更多…

在分治策略中，我们递归地求解一个问题，在每层递归中使用如下三个步骤： 分解（Divide）步骤将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。 解决（Conquer）步骤递归地求解出子 阅读更多…

2.1 渐进记号 2.1.1 θ 记号 θ()用来描述一个区间（给出了上界和下界），如下图，即0<=c_1g(n)<=f(n)<=c_2g(n). 其中常数c_1和c_2均大于0且都 阅读更多…

1.1 插入排序 下图为排序中的几组中间状态，代码下面有， 伪码： python代码实现： 1.2 分析算法 一般来说，算法需要的时间与输入的规模同步增长，所以通常把一个程序的运行时间描述成其输入规模 阅读更多…