INT102

INT102 Week3 分治思想和基础图论 关于递归的时间复杂度

大问题的计算次数 = 子问题的计算次数 + 计算子问题结果之间的过程所需次数

• 让T(n)表示n个数字上的二进制搜索算法的时间复杂性
  T ( n ) = { 1 ， i f n = 1 T ( n / 2 ) + 1 ， o t h e r w i s e T(n)=begin{cases} 1，if quad n=1\ T(n/2)+1， otherwiseend{cases} T(n)={1，ifn=1T(n/2)+1，otherwise​
• 三种T(n)对应的大O

T(n) = T(n/2)+1 T(n) is O(logn)

T(n) = 2T(n/2)+1 T(n) is O(n)

T(n) = 2T(n/2)+n T(n) is O(nlogn)

• 归并排序（Merge Sort -->O(nlogn)）

基本思想

1. 把数组从中间分成两个子数组
2. 一直递归把子数组划分成更小的子数组，直到子数组内只有一个元素
3. 依次按照递归的返回顺序，不断合并排好序的子数组，直到最后把整个数组顺序排好

代码实现：

#include 
#include 
void merge(int arr[],int tempArr[], int left, int mid, int right){
    //标记左半区第一个未排序的元素
    int l_pos = left;
    //标记右半区第一个未排序的元素
    int r_pos = mid + 1;
    //临时数组元素的下标
    int pos = left;
    
    //合并
    while(l_pos <= mid && r_pos <= right){//左半区和右半区都存在元素，即不不为单个元素子数组
        if(arr[l_pos] < arr[r_pos]){//左半区第一个元素更小
            tempArr[pos++] = arr[l_pos++];//将左半区位置的值赋给临时数组的位置，并往后延伸
        }else{
            tempArr[pos++] = arr[r_pos++];
        }
    }
    //合并左半区剩余的元素
    while(l_pos <= mid)
        tempArr[pos++] = arr[l_pos++];
    //合并右半区剩余的元素
    while(r_pos <= right)
        tempArr[pos++] = arr[r_pos++];
    //把临时数组中合并后的元素复制回原来的数组
    while(left <= right){
        arr[left] = tempArr[left];
        left++;
    }
}



//归并排序
void msort(int arr[],int tempArr[], int left, int right){
    //如果只有一个元素，那么就不需要继续划分
    //只有一个元素的区域，本身就是有序的，只要被归并即可
    if(left< right){
        //找中间点
        int mid = (left +right) / 2;
        //递归划分左半区
        msort(arr,tempArr,left, mid);
        //递归划分右半区
        msort(arr,tempArr, mid + 1, right);
        //合并已经排序的部分
        merge(arr,tempArr,left,mid,right);
    }
}


//归并排序入口
void merge_sort(int arr[], int n){
    //分配一个辅助数组
    int*tempArr = (int *)malloc(n* sizeof(int));
    if(tempArr){
        msort(arr, tempArr,0,n-1);
        free(tempArr);//数组分配成功
    }else{
        printf("error!");
    }
}

void print_arr(int arr[], int n){
    for(int i = 0; i
        printf("%d ", arr[i]);
    }
    putchar('n');
}

int main(int argc, const char * argv[]) {
    // insert code here...
    int arr[] = {9, 5, 2, 7, 12, 4, 3, 1, 11};
    int n=9;
    print_arr(arr, n);
    
    merge_sort(arr, n);
    print_arr(arr, n);
    return 0;
}

• 基础图论

无向图（undirected graph）

1. 在无向图中:设e = {u, v}是G的一条边，则

–>u和v是相邻的，称为彼此的邻居

–>e与u和v有关

• 节点的度(degree of a vertex v): 即deg(v)，节点相连的边的量(环路的度是节点v的两倍)
• 简单图(simple graph): 两个顶点之间最多有一条边，没有自循环(循环:顶点到自身的一条边)
• 多图(multigraph): 允许两个顶点之间有一条以上的边
• 伪图(pseudograph): 允许自循环

邻接矩阵(Adjacency 0matrix)：表示节点间连结与否或距离的矩阵 关联矩阵(incidence matrix)：表示节点与边关联与否或距离的矩阵

–M(i , j) = 1 如果边i是从顶点j出发的
–M(i , j) = -1 如果边i通向顶点j

关联列表(Incidence list): 表示最左边的一列与哪些点相连，如a与b，c相连

• 树(Tree)

定义：无向图G = (V, E)是无环且连续可构造的树

根节点	孩子节点	父母节点	度	叶子节点	内部节点	左子树
root	children	parent	degree	leaf	internal vertices	left subtree

二叉树：最多二度的树

(图源：https://blog.csdn.net/sanmusen_wu)
感谢学长的总结，希望可以借鉴。

树的遍历

• 前序遍历：v, L, R [0, 1, 3, 7, 8, 4, 9, 10, 2, 5, 11, 12, 6, 13, 14]
• 中序遍历 L, v, R [7, 3, 8, 1, 9, 4, 10, 0, 11, 5, 12, 2, 13, 6, 14]
• 后序遍历 L, R, v [7, 8, 3, 9, 10, 4, 1, 11, 12, 5, 13, 14, 6, 2, 0]

Breath-first search(BFS)

深度优先搜索(DPS): preorder, inorder, postorder遍历

• 欧拉回路（Euler circuit）

定义：图G中的欧拉电路是指只访问G的每条边一次的电路。

充要条件：

1. G为连通图，并且G仅有两个奇度结点（度数为奇数的顶点）或者无奇度结点。
2. 或D为有向图，D的基图连通，并且所有顶点的出度与入度都相等；
3. 或者除两个顶点外，D的其余顶点的出度与入度都相等，而这两个顶点中一个顶点的出度与入度之差为1，另一个顶点的出度与入度之差为-1。

• 哈密顿图（Hamiltonian circuit/path）

给定一个图，存在有一种一笔画能够走完这个图的所有节点（走过的边不可再走，不必经过所有边），也就是这个图的节点可以一笔画走完，则称这个图为哈密顿图。

部分题型

1. 给定一个递推公式，证明其O(n)为某值 --> 以某值为基础假设T(n)恒等式，证明T(n)有上界为O(n)乘一常数

2. 给定一棵树，按照前序中序后序对其遍历