随笔 - 13  文章 - 36  trackbacks - 0
<2009年10月>
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567

常用链接

留言簿(2)

随笔档案

友情链接

搜索

  •  

最新评论

阅读排行榜

评论排行榜

10 2009 档案
哈希结构      摘要: 哈希结构

C++博客 Alex-Lee 2009-10-21

哈希结构在处理大量数据时具有很好的优势,在插入,查询,删除等操作上具有常量的时间复杂度O(1)。使用范围是数据集具有自然数上的关键字域(不是自然数也需要能够转为自然数域),通过哈希函数将关键字映射到寻址数组的槽。由于关键字域U[0...n]与寻址数组[0...m]中,总是n>m,也就是说,总有多个关键字对应一个槽。这个碰撞就需要通过一些方法改变。可以通过拉链法(链表法)和开放地址法。对于拉链法中,链表不能太长,否则影响速度,最好控制在10个元素之内,这样就要去寻址数组长度m>= n/10,这样就会多消耗些空间。为了让每个链表长度基本一致,就需要  阅读全文
posted @ 2009-10-22 00:31 Alex-Lee 阅读(1867) | 评论 (5)  编辑
快速排序算法、计数排序算法      摘要: 快速排序算法、计数排序算法

C++博客 Alex-Lee 2009-10-20

快速排序是分治算法,将数组分为几部分,在各部分内完成排序,递归排序。算法时间复杂度O(nlgn)。这是比较排序算法中速度最快的一个算法了。计数排序、基数排序、桶排序算法是非比较排序算法,他们的算法复杂度是O(n)。快速排序算法在选取支点上要有技巧,最好能达到随即要求。
  阅读全文
posted @ 2009-10-20 22:18 Alex-Lee 阅读(1826) | 评论 (2)  编辑
优先级队列      摘要: 优先级队列

C++博客 Alex-Lee 2009-10-18

上篇随笔谈到了堆结构的一个应用就是堆排序算法,虽然堆排序算法性能不错,但是比起快速排序算法还是有些差距。但是堆结构的另外一个应该就比较广泛了,就是优先级队列。
优先级队列有3中操作:插入(O(lgn)),最大最小值(O(1)),删去最大最小值(O(lgn))。其算法性能很好,在优先级调度作业上应用比较广泛。基于优先级的调度算法中,基于堆结构的实现算法是一个比较好选择。在事件驱动的仿真器中也有应用。  阅读全文
posted @ 2009-10-18 18:49 Alex-Lee 阅读(1201) | 评论 (3)  编辑
堆排序算法      摘要: 堆排序算法

---------- C++博客 Alex-Lee 2009-10-15

(二叉)堆结构是一种数组对象,它可以被视为一颗完全二叉树。算法时间复杂度O(nlgn),具有插入排序和合并排序的优点。堆结构满足堆性质:对除根以外的每个节点i,满足A[PARENT(i)] >= A[i]。

堆排序算法实现有三个部分完成:
1,保持堆性质函数heap_ify;
2,构建堆函数build_heap;
3,堆排序函数 heap_sort;
另外,在优先级队列中有extract-max 过程和insert过程,在作业队列中常用,比如消息队列。这部分在优先级排序中说明。
  阅读全文
posted @ 2009-10-15 21:01 Alex-Lee 阅读(1590) | 评论 (1)  编辑