算法分析思想

1.迭代法

是一种不断用旧值递推新值的过程，分精确迭代和近视迭代。是用来求方程和方程组近似根的方法。

2.穷举搜索法

对可能的解的众多候选按照某种顺序逐一枚举和检验。典型的问题如选择排序和冒泡排序。

3.递归

递归算法执行过程分 递推 和 回归 两个阶段。在 递推 阶段，将大的问题分解成小的问题；在 回归 阶段，获得最简单问题的解后，逐级返回，依次得到稍微复杂情况的解，知道获得最终的结果

递归运行效率较低，因为有函数调用的开销，递归多次也可能造成栈溢出。

4.贪心算法

不追求最优解，只找到满意解。

找回零钱问题
装箱问题

5.分治法

将一个难以直接解决的大问题，分割成一些规模较小的相同问题，各个击破，分而治之。

大整数乘法
快速排序
归并排序
最大子数组和

6.动态规划DP

复杂问题不能分解成几个子问题，而分解成一系列子问题；

DP通常基于一个递推公式及一个(或多个)初始状态，当前子问题解由上一次子问题解推出。

动态规划算法的关键在于解决冗余，以空间换时间的技术，需要存储过程中的各种状态。可以看着是分治算法+解决冗余

使用动态规划算法的问题的特征是子问题的重叠性，否则动态规划算法不具备优势

7.回溯法

也叫 试探法。 是一种选优搜索法，按照选优条件搜索，当搜索到某一步，发现原先选择并不优或达不到目标，就退回重新选择。

  1. 针对问题，定义解空间（ 这时候解空间是一个集合，且包含我们要找的最优解）
  2. 组织解空间，确定易于搜索的解空间结构，通常组织成树结构 或 图结构
  3. 深度优先搜索解空间，搜索过程中用剪枝函数避免无效搜索

回溯法求解问题时，一般是一边建树，一边遍历该树；且采用非递归方法。

八皇后问题
迷宫问题

数据结构

1.散列表（哈希表）

散列表使用某种算法操作(散列函数)将键转化为数组的索引来访问数组中的数据，这样可以通过Key-value的方式来访问数据，达到常数级别的存取效率。现在的nosql数据库都是采用key-value的方式来访问存储数据。

散列函数

散列函数就是将键转化为数组索引的过程。且这个函数应该易于计算且能够均匀分布所有的键。

散列函数最常用的方法是除留余数法。这时候被除数应该选用素数，这样才能保证键值的均匀散步。

1
2
3
4
int hash = 0;
for (int i=0;i<s.length();i++){
	hash = (R*hash +s.charAt(i)%M);
}

解决碰撞(不同关键字散列地址相同为碰撞)

拉链法

将大小为M的数组中的每个元素指向一条链表，链表中的每个节点都存储了散列值为该元素索引的键值对。每条链表的平均长度是N/M，N是键值对的总个数。

添加操作：

  1. 通过hash函数得到hashCode
  2. 通过hashcode得到index
  3. 如果index处没有链表，建立好新结点，作为新链表的首结点
  4. 如果index处已经有链表，先要遍历看key是否已经存在，如果存在直接返回，如果不存在，加入链表头部

TODO 编写代码

删除操作：

  1. 通过hash函数得到hashCode
  2. 通过hashcode得到index
  3. 遍历链表，删除结点
线性探测法

使用大小为M的数组保存N个键值对，当碰撞发生时，直接检查散列表中的下一个位置。

二叉树

二叉查找树

  1. 左子树 < 根节点 < 右子树
  2. 任意左右子树也为二叉树
  3. 没有键值相等的节点

删除节点,需要重建排序树

1) 删除节点是叶子节点（分支为0），结构不破坏
2）删除节点只有一个分支(分支为1)，结构也不破坏
3）删除节点有2个分支，此时删除节点

n个节点的完全二叉树，其查找，删除的复杂度都是O(logN),但是如果频繁的插入删除，导致二叉树退化成一个n个节点的单链表，也就是插入，查找复杂度趋于O(N)，为了克服这个缺点，出现了很多二叉查找树的变形，如AVL树，红黑树，伸展树(splay tree)。

B树（balance tree）

平衡查找树，一种多路查找树。能保证数据插入和删除情况下，任然保持执行效率。

一个M阶的B树满足：

  1. 每个节点最多M个子节点
  2. 除根节点和叶节点外，其它每个节点至少有M/2个孩子
  3. 根节点至少2个节点
  4. 所有叶节点在同一层，叶节点不包含任何关键字信息
  5. 有k个关键字的页节点包含k+1个孩子(叶子结点的数目正好等于树中所包含的关键字总个数加1)

也就是说：
根节点到每个叶节点的路径长度都是相同的。

B+树

mysql索引使用B+树的数据结构

赫夫曼编码

通过字符出现的频率，优先级，二叉树进行的压缩算法。对一个字符串，计算每个字符出现的次数,把这些字符放到优先队列（priority queue），对这个priority queue转出二叉树

原则：出现频率越多的会在越上层，编码也越短，出现频率越少的在越下层，编码也越长。
不存在某一个编码是另一个编码的前缀,字符都在叶节点上，所以不会存在一个编码是另一个编码的前缀
二叉树每个节点要么是叶子节点，要么是双分支节点(且左分支编码为0，右分支编码为1)

平衡二叉树

排序算法

冒泡排序法

算法步骤：

  1. 比较相邻的两个元素，如果第二个比第一个大，就交换它们
  2. 对每一对相邻元素执行第一步，第一遍完成后，末尾的元素会是最大值
  3. 针对所有的元素重复以上的步骤，除了最后一个
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
#define SIZE 8
//冒泡排序算法
void bubble_sort(int a[], int n){
    int i,j,temp,count=0;
    for (j=0; j<n-1; j++) {
        //由于每次遍历后最后的位置逐渐由小到大排序，顾减少判断
        for (i=0; i<n-1-j; i++) {
            if (a[i]>a[i+1]) {
                count++;
                temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
            }
        }
    }
    printf("共交换了%d次",count);
}
int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    int arr[SIZE] = {6,7,3,2,5,12,5,11};
    
    bubble_sort(arr,SIZE);
    int i =0;
    for (i = 0; i < SIZE; i++)
    {
        printf("%d", arr[i]);
    }
    printf("\n");
    
    return 0;
}

最好时间复杂度O(n),最坏时间复杂度O(n^2)

快速排序算法

在平均状况下，排序 n 个项目要Ο(n log n)次比较

算法步骤：

1 从数列中挑出一个元素，称为 “基准”（pivot），

2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void quick_sort(int a[],int left,int right){
    if (left>=right) {
        return;
    }
    int i=left,j=right,key=a[left];
    while (i<j) {
        while (i<j && key<=a[j]) { //先进行j的从右向左找比key小的值
            j--;
        }
        a[i]=a[j];//找到时放到left索引的位置
        while (i<j && key>=a[i]) {//i的从左向右找比key大的值
            i++;
        }
        a[j]=a[i];
    }
    a[i]=key;//当在当组内找完一遍以后就把中间数key回归
    quick_sort(a, left,i-1);
    quick_sort(a,i+1, right);
}

选择排序算法

它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

  • 树形选择排序

利用满二叉树的性质，将输入的数据存放到满二叉树的叶节点，通过比较树中剩余可用节点（从底层的叶节点开始）的大小，每次选择最小的数值（比较复制到二叉树的顶端），并且把最小数值赋给排序数组的前端，把最小数值原来叶节点的位置设置为不可用；依次循环直至最后一个可用叶节点。

  • 堆排序

堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

总的比较次数为
1 + 2 + 3 + 4 +5 + . . . + n - 1 = n(n-1)/2, 时间复杂度是 O(n^2).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//选择排序算法
void select_sort(int a[],int n){
    int i,j,d,temp;
    for (i=0; i<n; ++i) {
        d=i;
        for (j=i+1; j<n; ++j) {
            if(a[j]<a[d]){
                d=j;
            }
        }
        if(d!=i){
            temp=a[d];
            a[d]=a[i];
            a[i]=temp;
        }
    }
}

一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void heapAdjust(int a[],int s,int n){
    int temp = a[s];
    int child=2*s+1;//左孩子结点的位置
    while (child<n) {
        if (child+1<n && a[child]<a[child+1]) {//右孩子大于左孩子
            ++child;
        }
        if(a[s]<a[child]){//子结点大于父结点,替换父结点
            a[s]=a[child];
            s=child;
            child=2*s+1;
        }else{
            break;
        }
        a[s]=temp; //当前待调整的结点放到比其大的孩子结点位置上
    }
}
void buildHeap(int a[],int n){
    int i;
    for (i=(n-1)/2; i>=0; i--) {
        heapAdjust(a,i,n);
    }
}
void heap_sort(int a[],int n){
    buildHeap(a,n);
    //从最后一个元素开始对序列进行调整
    int i;
    for (i=n-1; i>0; --i) {
        //交换堆顶元素H[0]和堆中最后一个元素
        int temp = a[i]; a[i] = a[0]; a[0] = temp;
        //每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
        heapAdjust(a, 0, i);
    }
}

二分查找算法

优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。适用于不经常变动而查找频繁的有序列表。时间复杂度为O(logn)。

算法步骤：

  1. 将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。
  2. 如 果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。
  3. 如果x>a[n/2]，则我们只要在数组a的右 半部继续搜索x。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//递归法
int binary_search(int a[],int value,int left,int right){
        int mid = (left+right)/2;
    if (left>right) {
        return -1;
    }
    if (a[mid]==value) {
        return mid;
    }else if(a[mid]>value){
        return binary_search(a, value, left, mid-1);//注意右边界设为mid-1，不然可能程序找到退出的条件
    }else{
        return binary_search(a, value, mid+1, right);
    }
}
//while循环
int binary_search_normal(int *a,int value,int n){
    int left=0,right=n-1;
    while (left<=right) {
        int mid = (left+right)/2;
        if (a[mid]==value) {
            return mid;
        }else if(a[mid]>value){
            right = mid -1;
        }else{
            left=mid+1;
        }
    }
    return -1;
}

归并排序算法

采用分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。速度仅次于快速排序，为稳定排序算法。

算法步骤：

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  4. 重复步骤3直到某一指针达到序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

    TODO
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//归并排序算法
void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex)
{
    int i = startIndex, j=midIndex+1, k = startIndex;
    while(i!=midIndex+1 && j!=endIndex+1)
    {
        if(sourceArr[i] >= sourceArr[j])
            tempArr[k++] = sourceArr[j++];
        else
            tempArr[k++] = sourceArr[i++];
    }
    while(i != midIndex+1)
        tempArr[k++] = sourceArr[i++];
    while(j != endIndex+1)
        tempArr[k++] = sourceArr[j++];
    for(i=startIndex; i<=endIndex; i++)
        sourceArr[i] = tempArr[i];
}
//内部使用递归
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{
    int midIndex;
    if(startIndex < endIndex)
    {
        midIndex = (startIndex + endIndex) / 2;
        MergeSort(sourceArr, tempArr, startIndex, midIndex);
        MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
        Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
    }
}

插入排序

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序时可用。法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。

直接插入排序算法

  1. 设置监视哨r[0]，将待插入纪录的值赋值给r[0]；
  2. 设置开始查找的位置j；
  3. 在数组中进行搜索，搜索中将第j个纪录后移，直至r[0].key≥r[j].key为止；
  4. 将r[0]插入r[j+1]的位置上。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insert_sort(int a[],int n)
{
    int i,j;
    int temp;
    for(i=1;i<n;i++)
    {
        temp=a[i];
        for(j=i;j>0&&a[j-1]>temp;j--)
        {
            a[j]=a[j-1];
        }
        a[j]=temp;
    }
}

希尔排序算法

shell排序是不稳定的，希尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。

排序过程：

  1. 先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；
  2. 然后取d2<d1，重复上述分组和排序操作；

  3. 直至di=1，即所有记录放进一个组中排序为止。

    TODO

BFPRT(线性查找算法)

时间复杂度
O(N)

算法步骤：

  1. 将n个元素每5个一组，分成n/5(上界)组。

  2. 取出每一组的中位数，任意排序方法，比如插入排序。

  3. 递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。

  4. 用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。

  5. 若i==k，返回x；若ik，在大于x的元素中递归查找第i-k小的元素。

终止条件：n=1时，返回的即是i小元素。

其它

二叉查找树

左孩子 < 根结点 <= 右孩子

红黑树

  • 根结点必须是黑色，空叶子结点是黑色的，红结点的叶子结点必须是黑色的

  • 左旋

  • 右旋

被旋转的树，在旋转前是二叉查找树，并且旋转之后仍然是一颗二叉查找树。

对x进行左旋，意味着，将“x的右孩子”设为“x的父亲节点”；对x进行右旋，意味着，将“x的左孩子”设为“x的父亲节点”

红黑树添加

  1. 将红黑树作为二叉查找树，插入结点
  2. 将插入的结点着色为红色（不会违背 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点 的性质）
  3. 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。

十大算法

1 快速排序算法

在平均状况下，排序 n 个项目要Ο(n log n)次比较

算法步骤：

1 从数列中挑出一个元素，称为 “基准”（pivot），

2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

2 堆排序算法

堆排序的平均时间复杂度为Ο(nlogn)

算法步骤：

1.创建一个堆H[0..n-1]

2.把堆首（最大值）和堆尾互换

3.把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置

4.重复步骤2，直到堆的尺寸为1

3 归并排序算法

算法步骤：

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  4. 重复步骤3直到某一指针达到序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

4 二分查找算法

　　二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜 素过程结束； 如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组 为空，则代 表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为Ο(logn) 。

5 BFPRT(线性查找算法)

BFPRT可以保证在最坏情况下仍为线性时间复杂度。算法在最坏情况下，依然能达到o(n)的时间复杂度

算法步骤：

  1. 将n个元素每5个一组，分成n/5(上界)组。
  2. 取出每一组的中位数，任意排序方法，比如插入排序。
  3. 递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。
  4. 用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。
  5. 若i==k，返回x；若ik，在大于x的元素中递归查找第i-k小的元素。
    终止条件：n=1时，返回的即是i小元素。

    6 DFS（深度优先搜索）

    DFS属于盲目搜索。一般用堆数据结构来辅助实现DFS算法。

深度优先遍历图算法步骤：

  1. 访问顶点v；
  2. 依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
  3. 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

7 BFS(广度优先搜索)

BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。

算法步骤：

  1. 首先将根节点放入队列中。
  2. 从队列中取出第一个节点，并检验它是否为目标。
    如果找到目标，则结束搜寻并回传结果。
    否则将它所有尚未检验过的直接子节点加入队列中。
  3. 若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
  4. 重复步骤2。

8 Dijkstra算法

Dijkstra 算法可以找到 s 到 t的最低权 重路径(例如，最短路径)。这个算法也可以在一个图中，找到从一个顶点 s 到任何其他顶点的最短路径。对于不含负权的有向图，Dijkstra算法是目 前已知的最快的单源最短路径算法。

算法步骤：

  1. 初始时令 S={V0},T={其余顶点}，T中顶点对应的距离值
    若存在，d(V0,Vi)为弧上的权值
    若不存在，d(V0,Vi)为∞
  2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S
  3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值
    重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

9 动态规划算法

算法步骤：

  1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
  2. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多 次。 动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题 时，只是 在表格中简单地查看一下结果，从而获得较高的效率。

10 朴素贝叶斯分类算法

朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类的基础是概率推理，就是在各种条件的存在不确定，仅知其出现概率的情况 下， 如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的，即假设样本每个特征与其他特征都不相关。