Posts Tagged "Algorithm"

二叉树基础

二叉树 二叉树定义 有且仅有一个根结点,除根节点外,每个结点只有一个父结点,最多含有两个子节点,子节点有左右之分。 二叉树节点 以Python举例,一个二叉树节点结构类似于下面这样,一般的面向对象的语言,定义二叉树节点都类似: # 二叉树节点 class TreeNode(object): def __init__(self, data = None, left = None, right = None): self.data = data self.left = left self.right = right 二叉树的遍历 遍历是二叉树的一个基本操作,主要有前序、中序、后序三种遍历方式。 先序遍历:根节点->左子树->右子树 中序遍历:左子树->根节点->右子树 后序遍历:左子树->右子树->…

算法基础_分析算法复杂度

1 算法 1.1 首先,什么是算法,我们一般这么定义算法: 算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令 ,算法代表着用系统的方法描述解决问题的策略机制。 也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出,所以,如果一个算法需要的时间或者控件是无限制的,那么这种算法我们认为是不可行的。 1.2 时间复杂度 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度(O是数量级的符号 ),简称时间复杂度。…