前言

学一些拓展内容

时间复杂度主定理

对于递归问题的时间复杂度计算，有主定理可以解决以下问题 有

树

有向递归结构

  1. 度(m)：节点的度为该节点子节点的个数，树的度为有最多子节点的节点的字节的个数，称为（树的度）次树
  2. 叶子：度为0
  3. 路径长度：经过分支数目
  4. 直接相连的：孩子，双亲，间接相连的：兄弟，一群的：子孙（直到叶子）、祖先（直到根节点）
  5. 层次：根节点为第一层
  6. 高度/深度(h)：最高层
  7. 有序/无序：兄弟节点是否有序
  8. 森林：无根节点的树
  9. 节点数(n)
  10. “满”前缀：叶子集中在最高层

二叉树：度不大于2的树，严格区分左右子树

完全二叉树：满二叉树可以依次删去最高层最右侧的叶子

理论式

节点数所有节点度数

层节点数

总节点数

遍历顺序

  1. 先根：根、左节点、右节点
  2. 后根：左节点、右节点、根
  3. 层序：从上到下、从左到右

关系存储结构

  1. 双亲：根节点指向-1/?，其他节点指向其双亲节点，适于从下向上搜索
  2. 孩子：节点存储指向所有孩子节点的“指针”，适于从上向下搜素
  3. 孩子兄弟：节点存储指向该层的兄弟节点和下一层的孩子节点，适于将多次树转化为二叉树

排序

这里指的“开头”“末尾”是泛指

  1. 稳定的：相同关键字经过排序后不改变相对次序
  2. 基于比较的排序算法最好的平均时间复杂度为

  1. 直接插入排序：分成有序/无序区，用无序区的开头元素挨个比较有序区元素查找插入位置后插入有序区

稳定，就地排序，正序、反序、平均

  1. 折半插入排序：分成有序/无序区，用无序区的开头元素折半查找插入位置后插入有序区

稳定，就地排序，（优于直接插入）平均

  1. 希尔排序：从开头向末尾遍历，向d个组轮流分发元素，对R[d]~R[n-1]进行各组内直接插入排序，然后减小d直到d=0

不稳定，就地排序，平均

  1. 冒泡排序：分成有序/无序区，用无序区的开头元素和有序区末尾元素进行关键字比较判断是否交换位置，交换则交换后再次先前比较，否则取无序区下一个元素比较

稳定，就地排序，（劣于直接插入）正序、反序、平均

  1. 快速排序：取待排序区域的一个元素进行排序（关键字大于的放于一侧，小于的放于一侧），然后分为两个区域递归进行直到没有元素或元素数为1

不稳定，就地排序，栈空间最优/最差/平均，时间复杂度最优/最差/平均（最差是有序的） 排序算法描述如下：取开头元素存入临时变量作为基准，设置头尾指示器指向元素头和元素尾，从后向前遍历直到两指示器重合或找到比基准小的元素，将该元素赋值给头指示器指向的元素，然后自增头指示器，接着从前到后遍历直到两指示器重合或找到比基准大的元素，将该元素赋值给尾指示器指向的元素，然后自减尾指示器，重复直到两个指示器重合，然后将基准元素赋值给已经重合的两指示器指向的元素，返回指示器值

int sort(int R[], int s, int t){
	int temp = R[s];
	int i = s, j = t;
	while(i < j){
		while(i < j && temp <= R[j]){
			j--;
		}
		if(i < j){
			R[i] = R[j];
			i++;
		}
		while(i < j && temp >= R[i]){
			R[j] = R[i];
			j--;
		}
	}
	R[i] = temp;
	return i;
}
  1. 简单选择排序：从无序区两两比较选出一个关键字最小的排到有序区末尾

不稳定，就地排序，平均

  1. 堆排序：小根堆（左子树小于等于根节点小于等于右子树）、大根堆（左子树大于等于根节点大于等于右子树）

不稳定，就地排序，最好、最坏、平均都是

  1. 归并排序：

待补充