算法学习笔记:顺序统计量

在一个由n个元素组成的集合中,第i个顺序统计量(order statistics)是该集合中第i小的元素,例如第1个顺序统计量是最小值,第n/2个顺序统计量是中位数(当n是偶数时,中位数一般指i=n/2的那个数)。顺序统计量问题就是给定包含n个(互异的)数的集合和整数i,找出第i小的数。

解决这个问题最直接的办法就是先排序,再直接找出第i个元素即可,排序最快的时间复杂度是$O(n \log n)$。但其实还可以更快地找到第i个顺序统计量,本文将主要介绍一个实用的随机算法和确定性算法,它们都可以在$O(n)$的时间内解决这个问题。

算法学习笔记:堆排序

相比归并排序和快速排序,本文将介绍另一种平均时间复杂度是$O(n \log n)$的排序方法——堆排序(Heap Sort)。堆排序使用了一种被称为“堆”的数据结构,这也是它相比其他两种排序方法的特殊之处。堆这种数据结构不仅可以用于排序,也可以用来维护优先级队列。本文最后还简要对比了快速排序和堆排序的优缺点。

算法学习笔记:快速排序

通常算法初学者都会接触到形形色色的排序算法,例如插入排序、选择排序、冒泡排序等等,这些排序算法都非常容易理解和上手,但是它们的时间复杂度是$O(n^2)$的。本文将介绍快速排序,同归并排序一样,它的时间复杂度是$O(n \log n)$。

对于包含n个数的输入数组来说,快速排序是一种最坏情况运行时间为$O(n^2)$的算法,但它通常是实际应用中最常用的排序算法,因为它的平均性能是$O(n \log n)$的,而且隐含的常数因子非常小,并能够进行原址排序。

算法学习笔记:主方法

上一篇算法学习笔记:分治法中,介绍了分治法及一些常见的分治法案例。其中递归式与分治方法是紧密相关的,因为使用递归式可以很自然地刻画分治算法的运行时间。一般来说,求解递归式有“代入法”,“递归树法”和“主方法”。其中主方法用于方便地求解形如$T(n)=aT(n/b)+f(n)$的递归式。

本文将介绍主方法的一个“简化版本”,虽然是简化的,但它依然可以满足日常大多数的算法分析,并且更好理解其含义,最后再给出一个主方法的简要证明过程。

算法学习笔记:分治法

在计算机科学中,分治法是一种很重要的算法。分治法字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题,直到最后子问题可以简单地直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如归并排序、快速傅立叶变换等。

本文将简要介绍分治法的基本步骤,再以归并排序为例,介绍分治法的具体应用以及如何分析其时间复杂度。最后再介绍几个用分治法解决的算法案例。

算法学习笔记:渐进分析

当算法问题的规模很小的时候,基本上在任何一台机器上都会以很快的速度计算出来,只有在问题规模较大的时候分析算法的效率才显得有意义。因此我们要研究算法的渐进效率,也就是关心问题的输入规模趋向无穷大时,算法的运行时间是如何增长的。

本文将以插入排序为例,简要分析其运行时间。这种分析将引入一种关注时间如何随着输入规模增加而增加的记号。在此基础上,再给出几种标准方法来简化算法的渐进分析。

Console2:Windows命令行威力加强版

作为一个Windows重度用户+程序猿,日常开发中免不了要经常使用命令行工具。但是Windows下默认的cmd提供的功能实在有限。今天无意间发现了一款很不错的命令行工具前端Console2,瞬间就被其深深地吸引,赶紧记下来分享一下。本文将简单介绍Console2及其配置方法,让你可以快速地配置出一个类似Linux终端的装逼利器。

HTTP学习笔记:缓存

Web缓存是可以自动保存常见文档副本的HTTP设备。当Web请求抵达缓存时,如果本地有“已缓存的”副本,就可以从本地存储设备而不是原始服务器中提取这个文档。使用缓存可以减少冗余的数据传输,环节网络瓶颈的问题,降低对原始服务器的要求以及降低距离时延。

本文解释了缓存怎样提供性能降低费用,如何去衡量其有效性以及将缓存置于何处可以发挥它的最大作用。此外还会解释HTTP如何保持已缓存副本的新鲜度,缓存如何与其他缓存和服务器通信等问题。

当前网速较慢或者你使用的浏览器不支持博客特定功能,请尝试刷新或换用Chrome、Firefox等现代浏览器