雅乐网

计算机技术博客

算法

选取算法:中位数和第k小数

选取算法:中位数和第k小数

选取序列的第i小元素又称为选择问题,第i小的元素又称为第i个顺序统计量。简单的,排序之后我们可以立即找到第i小的元素,这种方法的时间复杂度是排序的时间复杂度,下界是O(nlogn)。但是选取第i小元素显然和排序相比要更简单,所以我们有理由相

计数排序和基数排序

计数排序和基数排序

基于比较的排序的时间复杂度下界是O(nlogn),但是当要排序的元素具有一些特殊性质的时候,可以使用非比较的方法突破这种限制。 计数排序 当待排序的元素a[]都是位于区间[0,k]中的整数时,可以使用计数排序。计数排序顾名思义就是统计元素的

基于比较的排序算法的下界

基于比较的排序算法的下界

在排序的结果中,各个元素的次序依赖于他们之间的比较,这种排序算法叫做比较排序。基于比较的排序有O(n^2)的冒泡排序、插入排序等,也有O(nlogn)复杂度的归并排序、堆排序等。实际上,O(nlogn)在渐进意义上是最优的。 假设我们有n个

堆和堆排序

堆和堆排序

数据结构中的堆和程序语言中的堆的意义并不相同,这里的堆是一种数据结构。二叉堆可以分为最大堆和最小堆,这里介绍最大堆。在最大堆中,结点的值满足堆的性质:除了根节点外,所有结点都不会比它的父节点大。 可以看到,逻辑上的堆是二叉树,但堆的物理结构

向量叉积和应用:判断点是否在三角形内部

向量叉积和应用:判断点是否在三角形内部

本文是学堂在线计算几何课程 凸包一章的部分学习笔记。如果要求编程判断一个点是否在三角形(三个点)内部。 可以看出,如果点在三角形的内部,沿着三边走一圈,这个点相对于行进路径始终保持相同方向(图中一直在左边); 如果点在三角形的外部,沿着三条

用两个栈模拟队列,快速获得队列的最大值

用两个栈模拟队列,快速获得队列的最大值

队列是一种常用的数据结构。如果按照常规的想法,要获得队列中的最大值,必须遍历队列中的所有元素,时间复杂度为O(n)。怎么降低这个时间呢?求最大元素很容易想到堆。如果建立一个辅助的最大堆(里面存放队列中元素的指针以及值),入队或者出队的时候,

使用主定理求解递归式

使用主定理求解递归式

算法导论中的4.5节介绍了一个用于求解递归式的主定理,可以用来求解部分形如下面形式的递归式: ,其中a>=1 , b >1 ,其中a>=1 , b >1 描述的算法 把规模为n的问题分为a个子问题,每个子问题规模是n

详解快速排序

详解快速排序

快速排序通常是在实际应用中排序的最好算法,虽然在最坏情况下它的时间复杂度是O(n^2),但是在平均情况下,它的时间复杂度是O(nlogn),并且它的常数因子非常小,因此效率极高。 下面的描述中对数组a中的[lo,hi)进行排序。([lo,h

最大子列和问题

最大子列和问题

给定K个整数组成的序列{ N1, N2, …, NK },“连续子列”被定义为{ Ni, Ni+1, …, Nj },其中 1 <= i <= j <= K。“最大子列和”则被定义为所有连续子列元素

归并排序

归并排序

归并排序是分治思想的典型应用。它的基本步骤有3步: 1. 划分。将要排序的数组分为两部分。 2. 递归求解。分别递归使用归并排序将两部分排序。 3. 合并。将两个有序的序列合并为一个有序的序列。 将序列分为两部分用时O(1),而对子序列进行