树，时间复杂度 个人总结_树的时间复杂度

一.数据结构 树

1.树的基本概念

拥有同一个父结点的结点称为兄弟结点。结点子树的根称为该结点的孩子，同时该结点为孩子的双亲。
结点的度为一个结点所包含子树的数量，而一个树中最大的结点的度就是树的度。
从根节点算起，根节点为第一层，往下递增层，而树的高度为树中结点最大层数。

2.二叉树

在二叉树的第i层最多有2的i-1次方个结点
具有n个结点的完全二叉树高度为（log2n）+1，（括号内向下取整）
二叉树有四种遍历方式 分别为

先序遍历

简单理解为从树的根节点开始，经过左子树，再到右子树
递归算法，root==null为退出条件，实现从根->左->右读取数据。

遍历算法，数据结构的出入栈，栈的入栈中注意right元素先入栈，因为栈具有后进先出的特性，根据栈的定义，每次进栈的元素都被放在原栈顶元素之上成为新的栈顶，而每次出栈的总是当前栈中最新的元素，故这样也能实现读数根->左->右。

中序遍历

读数 左->根->右

后序遍历

读数 左->右->后

层序遍历

读数是一层一层往下推的，推荐去试试leetcode的括号匹配题

3.二叉查找树

之所以有二叉查找树，是因为二叉查找树要求节点下左孩子比结点小，右孩子比结点大，那么查找的时候每次都只用查找一边

但是假如一直来的数都比结点要小，即一直往左或往右延展，二叉查找树会退化为链表

AVL树

针对上述二叉查找树极端情况下退化为链表，提出了AVL树的概念
AVL树是一种自平衡二叉树，且左右子树高度差绝对值不超过1
空树，左右子树都是AVL

非AVL树则需要旋转，提出平衡因子
getHeight[(left-getHeight)-(right-getHeight)
一个结点左右情况分析
2 1时，右旋
2 -1时，左，右旋
-2 -1时，左旋
-2 1时，右，左旋


伪码实现

left=pre.left;//保存b结点地址
pre.left=left.right;//e的值赋给b结点
left.right=pre;//pre值赋给b节点
return left;//返回节点地址，作为p的右孩子  
1
2
3

简单讲，右旋-自己变成左孩子的右孩子
左旋-自己变成右孩子的左孩子
简单讲，右旋-自己变成左孩子的右孩子
左旋-自己变成右孩子的左孩子

二.时间复杂度

（1）时间频度 一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

（2）时间复杂度 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。

算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。

记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),。
另外，在时间频度不相同时，时间复杂度有可能相同，
如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。
按数量级递增排列，常见的时间复杂度有：

常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),…， k次方阶O(nk),指数阶O(2n)。
随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

（3）求解算法的时间复杂度的具体步骤是：

⑴ 找出算法中的基本语句；

算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

⑵ 计算基本语句的执行次数的数量级；

只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。

⑶ 用大Ο记号表示算法的时间性能。

将基本语句执行次数的数量级放入大Ο记号中。

举例说明

(1)、O(n2)

2.1. 交换i和j的内容

sum=0； （一次）
for(i=1;i<=n;i++) （n+1次）
for(j=1;j<=n;j++) （n2次）
sum++； （n2次）
解：因为Θ(2n2+n+1)=n2
（Θ即：去低阶项，去掉常数项，去掉高阶项的常参得到），所以T(n)==O(n2)；

(4)、O(log2n）

i=1; ①
while (i<=n)
i=i*2; ②
解： 语句1的频度是1,

      设语句2的频度是f(n),   则：2^f(n)<=n;f(n)<=log2n    

      取最大值f(n)=log2n,

      T(n)=O(log2n )
1
2
3
4
5

类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。

如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；
当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；

当一个算法的空I司复杂度与n成线性比例关系时，可表示为0(n).

若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；

若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。