Tag Archives: 算法技术手册

算法技术手册 – 查找 – 散列查找(Hash查找)

对于含有n个元素的集合C,我们先构造一个Hash函数,让n映射到b个桶内,当选择合理时,速度会很快,时间复杂度O(1)。

完美哈希函数:不会产生冲突,是存在的。

对于>=1个值映射到同一个桶的情况下,就会发生碰撞。处理方法:

  • 链表:每个桶拉一个链表,第一遍散列后,在链表中查找是否存在元素。
  • 开放定址:构造双变量散列函数h(u, j)。h(u, 0) = h(u),此时退化为原始散列函数。

开放定址,分两类:

  • 线性探测h(u, j)=(h(u)+j) m[……]

继续阅读

算法技术手册 – 查找 – 二分查找

二分查找,要求集合是有序的,在这个条件基础上,它比顺序查找具有更好的性能。

如果使用伴随数组,只需要struct中有一个key是有序的就行。

需要指出的是,当数组放在磁盘上时,时间复杂度就不再是O(LogN),而取决于磁盘存取的开销。

源代码:

二分查找的变种:

1、支持快速插入和删除:由于原始集合是有序的,插入、删除都需要移动平均一半的数组。衍生出散列查找和平衡二叉树。

2、支持磁盘I/O:当数[……]

继续阅读

算法技术手册 – 查找 – 顺序查找

顺序查找也叫线性查找,是最简单的查找算法。穷举法遍历每个元素,查找是否包含元素t。

平均、最坏性能O(N)

如果目标元素t的分布是不均匀的,则有一些优化的方法。

  • 被找到的元素t有可能被再次找到:成功找到则移动到最前面。
  • 被找到的元素有更大可能性被找到:成功找到则向前移动一位(冒泡到前面),避免了上面方法中大量移动的耗时操作。且最终,反复被找到的元素会被冒泡到最前面。
  • 如果元素不会被多次查找到:成功找到则移[……]

继续阅读

算法技术手册 – 排序 – 如何选择排序算法

实际上,没有绝对优秀的、应该始终采用的排序算法。

书上给出了一些选择不同排序算法的理由,写的非常好,抄录一下。

  • 元素很少:插入排序
  • 几乎有序:插入排序
  • 关注最差情况:堆排序(牢记:堆排序的最差时间复杂度依然是O(nlogn))
  • 平均较好:快速排序
  • 元素从密集范围取出:桶排序
  • 代码量小:插入排序

书上也在不同应用环境:字符串、浮点、几乎有序等情况下进行了测试,有兴趣的可以去翻阅。

算法技术手册 – 排序 – 桶排序/哈希排序/散列排序

在前面的计数排序中,我们已经领略到了如何用空间换时间的方法,找到一种线性时间复杂度O(N)的排序算法。

计数排序的缺点也是非常明显的:一旦数据范围[0,k),中的k]相对于数据量N非常稀疏,计数排序的空间会非常大、时间消耗也会增大非常大。当然主要还是空间问题。

个人认为:桶排序 = 哈希排序 = 散列排序,基本思想是一样的。

于是桶排序/哈希排序应运而生,假设值域范围还是k,我们不去创建k个buckets,而是创建m个木桶,让N个元素通过哈系函数映射到这k个桶即可。这里还有一个[……]

继续阅读