存档

‘算法’ 分类的存档

有限状态机

2014年3月8日 没有评论

有限状态机的描述

有限状态机(英语:finite-state machine,缩写:FSM)又称有限状态自动机,简称状态机,是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。

在描述有限状态机时,状态、事件、转换和动作是经常会碰到的几个基本概念。

状态(State):指的是对象在其生命周期中的一种状况,处于某个特定状态中的对象必然会满足某些条件、执行某些动作或者是等待某些事件。

事件(Event):指的是在时间和空间上占有一定位置,并且对状态机来讲是有意义的那些事情。事件通常会引起状态的变迁,促使状态机从一种状态切换到另一种状态。

转换(Transition):指的是两个状态之间的一种关系,表明对象将在第一个状态中执行一定的动作,并将在某个事件发生同时某个特定条件满足时进入第二个状态。

动作(Action):指的是状态机中可以执行的那些原子操作,所谓原子操作指的是它们在运行的过程中不能被其他消息所中断,必须一直执行下去。
阅读全文…

分类: 算法 标签:

深度优先搜索算法的通用解法

2014年3月3日 没有评论

一、深度优先搜索

深度优先搜索算法(Depth First Search),是图论中的经典算法。
深度优先搜索算法是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当结点所有子结点那一层都被搜索过,再回溯返回到当前结点的邻结点,继续搜索,直到遍历完整棵树。一般采用的是前序遍历,先根然后再左右结点的方式进行。 阅读全文…

算法系列之 计数排序

2013年11月12日 没有评论

计数排序

之前讲的各种排序算法:插入排序、选择排序、冒泡排序、归并排序、快速排序、堆排序和希尔排序等,这些排序算法复杂度都不是线性的。
有没有可能找到一种线性的排序算法? 答案是肯定的。只要我们不比较,不交换元素,而在扫描到元素的时候,就能确定此元素在有序序列中的位置,就可以达到线性算法复杂度。这种排序叫计数排序。
它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法。
阅读全文…

分类: 算法 标签:

算法系列之 希尔排序

2013年11月12日 没有评论

希尔排序

希尔排序是一种分组插入排序,是插入排序的一种更高效的改进版本.
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
  •      插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率
  •      但插入排序一般来说是低效的, 因为插入排序每次都只能将数据移动一位

阅读全文…

分类: 算法 标签:

算法系列之 堆排序

2013年11月11日 没有评论

二叉堆的性质

  1. 二叉堆是一颗完全二叉树,最后一层的叶子从左到右排列,其它的每一层都是满的
  2. 最小堆父结点小于等于其每一个子结点的键值,最大堆则相反
  3. 每个结点的左子树或者右子树都是一个二叉堆

阅读全文…

分类: 算法 标签:

算法系列之 快速排序优化

2013年11月8日 没有评论

继上篇说了快速排序的实现原理:通过选择左边第一个数为轴值,分区让轴值左边的数都小于等于轴值并且右边都大于轴值,返回轴值并对左序列跟右序列进行递归处理

如果要排序的序列是基本有序的,这时选择左边第一个数为轴值,递归都只是对右边序列进行递归,会导致快速排序算法时间复杂度为N*N。 阅读全文…

分类: 算法 标签:

算法系列之五 快速排序

2013年11月8日 没有评论

快速排序的基本思想是:

1、选择轴值:pivot
2、分割,并返回轴值位置:将序列划分为两个子序列L和R,使得L中所有记录都小于或等于轴值,R中记录都大于轴值
3、递归处理:对子序列L和R递归进行快速排序 阅读全文…
分类: 算法 标签:

算法系列之四 归并排序

2013年11月3日 没有评论

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
阅读全文…

分类: 算法 标签: