女王控的博客

算法

8 篇文章

查找算法java实现

无序链表的顺序查找 特点 在含有N对键值的基于(无序)链表的符号表中,未命中的查找和插入操作都需要N次比较。命中的查找在最坏情况下需要N次比较。特别的,向一个空表中插入N个不同的键需要 次比较 实现 有序数组的二分查找 特点 在N个键的有序数组中进行二分查找最多需要(lgN+1)次比较(无论是否成功)。 向大小为N的有序数组中插入一个新的元素在最坏情况下需要访问~2N次数组,因此向一个空符号表中插入N… »

排序算法java实现

选择排序 思路 首先,找到数组中最小的那个元素,其次,将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。再次,在剩下的元素中找到最小的元素,将它与数组的第二个元素交换位置。如此往复,直到将整个数组排序。 特点 对于长度为 N 的数组,选择排序需要大约 次比较,N 次交换 运行时间和输入无关,其他算法会更善于利用输入的初始状态 数据移动是最少的,每次交换都会改变两个数组元素的值,因此选择排序用了 N… »

动态连通性(网络连通、等价性)

加权quick-union算法 特点 对于N个触点,加权quick-union算法构造的森林中的任意节点的深度最多为lgN。 对于加权quick-union算法和N个触点,在最坏情况下find()、connected()和union()的成本的增长数量级为logN。 实现 »

0%