算法

算法学习笔记

Posted by W-M on July 15, 2018

算法学习笔记

排序算法

插入排序——适合小数据量使用

将给定数组按照升序排序，属于稳定排序，最好情况下时间复杂度o(n)-数组顺序,最坏o(n2)-数组逆序,空间复杂度o(1),平均时间复杂度o(n2)

void insertion_sort(int *a, size_t size)
{
    int i, j, t;
    for(i = 1; i < size; i++){
        t = a[i];
        j = i - 1;
        while(j >= 0){
            if(a[j] > t){
                a[j + 1] = a[j];
            }
            else
                break;
            j--;
        }
        j += 1;
        a[j] = t;
    }
}

选择排序

首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。

不稳定，时间o(n2)，空间o(1)。涉及到元素的交换，类似于快排，将排在前面的元素交换到了与其相等的在原来其后面的元素的后面。

冒泡排序

冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数 放后。然后比较第2 个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较 （因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个 数），将小数放前中，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟 结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。

归并排序

分治：自顶向下，自底向上。稳定的，时间O(nlgn)，空间O(n)。

自顶向下，化整为零

static int[] aux;

static void merge_sort(int[] a) {
    aux = new int[a.length];
    merge_sort(a, 0, a.length - 1);
}

static void merge_sort(int[] a, int lo, int hi) {
    if (hi <= lo) {
        return;
    }
    int mid = (lo + hi) / 2;
    merge_sort(a, lo, mid);
    merge_sort(a, mid+1, hi);
    merge(a, lo, mid, hi);
}

static void merge(int[] a, int lo, int mid, int hi) {
    int l = lo, r = mid + 1, k = 0;
    while (true) {
        if (l > mid) {
            for (; r <= hi; r++) {
                aux[k++] = a[r];
            }
            break;
        }
        if (r > hi) {
            for (; l <= mid; l++) {
                aux[k++] = a[l];
            }
            break;
        }
        if (a[l] <= a[r]) {
            aux[k++] = a[l++];
        } else {
            aux[k++] = a[r++];
        }
    }
    for (int i = 0; i < k; i++) {
        a[lo++] = aux[i];
    }
}

自底向上，循序渐进

时间复杂度分析：总问题复杂度=子问题复杂度 + 每次递归的时间复杂度，可画出递归树进行计算。

堆排序

堆是一颗完全二叉树，堆排序的算法涉及到堆的初始化、堆上浮、堆下沉。最大堆与最小堆的区别仅在于下沉和上浮条件的不同。

时间复杂度O(nlogn),原地排序即空间复杂度O(1)，不稳定。

以最大堆为例，堆初始化就是一个从最后一个非叶节点开始不断下沉的过程。

堆排序中最重要的就是对于下沉操作的实现。

static void heap_sort(int[] a) {
    heap_init(a);
    int size = a.length - 1;
    while (size >= 0) {
        System.out.println(heap_delete(a, size--));
    }
}

/**
 * 对堆初始化
 * @param a
 */
static void heap_init(int[] a) {
    for (int i = (a.length/2) - 1; i >= 0; i--) {
        heap_sink(a, a.length - 1, i);
    }
}

/**
 * 删除堆顶元素
 * @param size : 堆的大小(堆中元素数-1)
 * @param a
 */
static int heap_delete(int[] a, int size) {
    int temp = a[0];
    a[0] = a[size--];
    heap_sink(a, size, 0);
    return temp;
}

/**
 * 对堆中第 k(第0个元素为根节点) 个元素进行下沉操作(小顶堆)
 * @param a
 * @param size : 堆的大小(堆中元素数-1)
 * @param k
 */
static void heap_sink(int[] a, int size, int k) {
    int min = Integer.MAX_VALUE, pos = -1;
    // 存在子节点
    if (2*k + 1 <= size) {
        min = a[2*k + 1];
        pos = 2*k + 1;

        if (2*k + 2 <= size) {
            if (a[2*k + 1] > a[2*k + 2]) {
                min = a[2*k + 2];
                pos = 2*k + 2;
            }
        }
    }

    if (min < a[k]) {
        exchange(a, k, pos);
        heap_sink(a, size, pos);
    }
}

static void exchange(int[] a, int i, int pos) {
    int temp = a[i];
    a[i] = a[pos];
    a[pos] = temp;
}

快速排序

时间复杂度O(nlogn),最差o(n2)(初始时数组有序，不管是顺序还是逆序，树高为n，每次切分时的时间复杂度为o(n),整体O(n2)),最好O(nlogn),平均O(nlogn)。 原地排序，空间O(1)。

实现例子：
快排图示

图1：快排图示(选最后一个元素为比较参数)

代码： 快排代码

图2：快排代码(选最后一个元素为比较参数)

快排为什么是不稳定的：(由于要实现原地排序，就需要交换操作，交换导致了不稳定) 快排为何不稳定

图3：快排为何不稳定

要想使快排稳定，需要新开O(n)空间(维护两个链表：比参数小的元素的链表、比参数大的元素组成的链表，不使用数组内元素交换方式)。

如何尽量保证快排高效：

  • 打乱初始数组，保证初始数组随机
  • 每次在数组内取的初始参数尽量随机，而不是每次均取第一个或者最后一个

归并排序每次递归都要用到一个辅助表，长度与待排序的表长度相同，虽然递归次数是O(log2n)，但每次递归都会释放掉所占的辅助空间，所以下次递归的栈空间和辅助空间与这部分释放的空间就不相关了，因而空间复杂度还是O（n）。

快速排序空间复杂度只是在通常情况下才为O(log2n)，如果是最坏情况的话，很显然就要O(n)的空间了。当然，可以通过随机化选择pivot来将空间复杂度降低到O(log2n)。

static void quick_sort(int[] a) {
    quick_sort(a, 0, a.length - 1);
}

static void quick_sort(int[] a, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    int p = partition(a, lo, hi);
    quick_sort(a, lo, p-1);
    quick_sort(a, p+1, hi);
}

/**
 * 以数组a中最后一个元素的值进行分割
 * @param a
 */
static int partition(int[] a, int lo, int hi) {
    int temp = hi--;
    while (true) {
        while (lo <= hi && a[lo] <= a[temp]) {
            lo++;
        }
        while (hi >= lo && a[hi] > a[temp]) {
            hi--;
        }
        if (lo >= hi) {
            break;
        }
        exchange(a, lo, hi);
    }
    exchange(a, lo, temp);
    return lo;
}

非比较排序

任何比较排序算法在最坏情况下都要用O(nlgn)次比较来进行排序，但此下界对于以非比较的操作来确定排序顺序的算法(计数排序、基数排序、桶排序)来说是不适用的。

计数排序

计数排序是一种非常快捷的稳定的排序方法，时间复杂度O(n+k),其中n为要排序的数的个数，k为要排序的数的最大值。计数排序对一定量的整数排序时候的速度非常快，一般快于其他排序算法。但计数排序局限性比较大，只限于对整数进行排序。计数排序是消耗空间发杂度来获取快捷的排序方法，其空间发展度为O（K）同理K为要排序的最大值。

计数排序的基本思想为一组数在排序之前先统计这组数中其他数小于这个数的个数，则可以确定这个数的位置。例如要排序的数为 7 4 2 1 5 3 1 5；则比7小的有7个数，所有7应该在排序好的数列的第八位，同理3在第四位，对于重复的数字，1在1位和2位（暂且认为第一个1比第二个1小），5和1一样位于6位和7位。

计数排序使用的三个数组：A代表原数组，B代表排序后数组，C代表数组中每个数出现次数的计数。

由于C的长度等于于数组A中元素的最大值，所以计数排序通常是不被使用的。A中元素最大值太大比如2^31,会导致数组C所需空间太大。

基数排序

稳定排序，桶排序的扩展。代码实现时基础数据结构为数组+链表或者二维数组。示意图如下：
基数排序

图4：基数排序

LSD：最低位优先的基数排序:思路为从最低位开始依次进行散列收集，重复此过程直到最高位执行完毕。

int maxLength = String.valueOf(getMax()).length();
int[][] radix;
int[] index;
for (int i = 0; i < maxLength; i++) {
    radix = new int[10][data.length];
    index = new int[10];
    Arrays.fill(index, 0);
    int pider = (int) Math.pow(10, i);  //  使用做除法然后取余的方法来取出某一位
    //  分配桶
    for (int j = 0; j < data.length; j++) {
        int temp = data[j];
        int key = temp / pider % 10;
        //  某个桶中数据增加之后，对应的计数器要加1
        radix[key][index[key]] = temp;
        index[key]++;
    }
    //  拼接桶中的数据
    int counter = 0;
    for (int j = 0; j < 10; j++) {
        for (int k = 0; k < index[j]; k++) {
            data[counter] = radix[j][k];
            counter++;
        }
    }
}

MSD：最高位优先的基数排序:

int maxLength = String.valueOf(getMax()).length();
int pider = (int) Math.pow(10, maxLength - 1);
data = msdIterationSort(data, pider);

/**
 * 迭代的msd排序
 * @param data 待排序数组
 * @param pider 用于取出数位的除数
 * @return
 */
private int[] msdIterationSort(int[] data, int pider) {
    int[][] radix = new int[10][data.length];
    int[] index = new int[10];
    Arrays.fill(index, 0);
    int sum = 0;
    //  将数分配到对应的桶中
    for (int j = 0; j < data.length; j++) {
        int pos = data[j] / pider % 10;
        radix[pos][index[pos]] = data[j];
        index[pos]++;
    }
    //  得到下一次迭代所用的除数
    pider = pider / 10;
    //  如果除数大于0，则需要对桶中的数据进行下一次迭代
    if (pider > 0) {
        //  对每个桶都要再次迭代
        for (int i = 0; i < 10; i++) {
            //  需要对桶的大小进行处理，因为创建桶的时候长度为待处理数据的长度，
            //  需要创建一个新数组来存放原来桶中的数据，然后用做下一次迭代
            int[] temp = new int[index[i]];
            for (int j = 0; j < index[i]; j++) {
                temp[j] = radix[i][j];
            }
            radix[i] = msdIterationSort(temp, pider);
        }
    }
    //  除数不大于0的时候说明对数的每一位都处理完了，接下来将每个桶中的数据拼接起来得到排好序的数据
    //  然后返回排好序的数据
    for (int i = 0; i < 10; i++) {
        sum = sum + index[i];
    }
    int[] result = new int[sum];
    int counter = 0;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < index[i]; j++) {
            result[counter] = radix[i][j];
            counter++;
        }
    }
    return result;
}

基数排序也是一种不基于比较并且稳定的排序算法，最优时间复杂度O(d(n + rd))，最差时间复杂度O(d(r + n))，平均时间复杂度O(d(n + rd))，其中r代表关键字的基数，d代表最大数据的长度，n代表关键字的个数。空间复杂度O(rd + n)（不确定最低位优先级排序和最高位优先级排序的空间复杂度是否一致，感觉最高位优先级排序的空间复杂度要更高些）

最低位优先级排序更适合数据集中数据最高位数不多的情况，当数据集中数据最高位数多时宜使用最高位优先级排序。

桶排序

桶排序，又称箱排序，与基数排序类似，也是使用哈希函数将数据映射到桶中，但与基数排序不同的是，将这个数映射到桶中之后，如果两个数据进入同一个桶，这个桶中将会进行排序来使桶中的数有序。

基本思路：

1、根据哈希函数，创建二维数组data，行数为基数的个数，列数为待排序数组的长度

2、遍历数组，将数组中的数放入对应的桶中，如果桶中使用的是插入排序，可以在这一步开始排序，如果使用的是快速排序，则等遍历完数组后再排序

3、排好序后，将各个数组拼接起来得到排好序的数组

桶排序的java实现（桶中使用插入排序，哈希函数为H(x) = x % 10）：

bucket = new int[10][data.length];
index = new int[10];
Arrays.fill(index, 0);

int pider = (int) Math.pow(10, String.valueOf(getMax()).length() - 1);
for (int i = 0; i < data.length; i++) {
    int pos = data[i] / pider;
    //  将新数值放入桶中之后，桶中的数据变为无序，
    //  由于除放在最后的那个数之外，其余的数都是有序的，因此考虑使用插入排序来使桶中的数据重新有序
    bucket[pos][index[pos]] = data[i];
    index[pos]++;
    if (index[pos] <= 1) {  //  桶中只有一个数据时，不需要插入排序，继续循环
        continue;
    }
    //  基本插入排序
    for (int j = index[pos] - 1; j > 0; j--) {
        if (bucket[pos][j] < bucket[pos][j - 1]) {
            swap(j, j - 1, bucket[pos]);
        } else {
            break;
        }
    }
}
int counter = 0;
for (int i = 0; i < 10; i++) {
    counter = getBucketResult(i, counter);
}

/**
 * 取出桶中的数据，并且返回下一个放入data中的数据应存放的位置
 * @param pos 桶的编号
 * @param counter 下一个放入data中的数据应存放的位置
 * @return
 */
private int getBucketResult(int pos, int counter) {
    for (int i = 0; i < index[pos]; i++) {
        data[counter] = bucket[pos][i];
        counter++;
    }
    return counter;
}

桶排序的最优时间复杂度为O(n)，最差时间复杂度取决于桶中的排序算法，如果是插入排序则为O(n2)，堆排序为O(nlogn)。空间复杂度为O(d + n)，d为基数个数，n为待排序数组长度。

提高桶排序的效率就要减少每个桶中的数据，极限情况下每个桶中只有一个数据，时间复杂度可以达到O(n)，但是会浪费巨大的空间，这是时间和空间的权衡问题。在数据规模合适的情况下，桶排序的表现可以优于快排等基于比较的排序算法，因为桶排序不是基于比较的排序算法。

最后是各种排序算法的比较图：
各种排序算法比较图

图5：各种排序算法比较图

算法思想

分治

分治策略就是将原问题划分成n个规模较小而结构与原问题相似的子问题，递归的解决这些子问题，然后再合并其结果，就得到原问题的解。其实现常常涉及到递归算法。

分治模式在每一层递归上都有三个步骤：

  • 分解：将原问题分解为一系列子问题
  • 解决：递归的解决子问题，若子问题足够小，则直接求解
  • 合并：将子问题的解合并为原问题的解

应用举例：归并排序，数组逆序对计数(采用了归并排序的思想)，矩阵相乘简化、快速找到数组中第i小的元素(快排中分割的思想与分治法相结合)

分治法的关键是算法的Combine。究竟应该怎样合并，目前没有统一的模式，因此需要对具体问题进行具体分析，以得出比较好的合并算法。

适用分治思想的算法：二分搜索、归并排序、快速排序、大整数乘法、Strassen矩阵乘法、汉诺塔、第K小元素、最近点对、快速傅里叶变换等。

动态规划

与分治法类似，动态规划法也是把问题一层一层地分解为规模逐渐减小的同类型的子问题。动态规划通常用来求最优化问题。此类问题可以有很多可行解，我们求出的是一个最优解，因为可能存在多个最优解。

分治法：子问题是相互独立的，若不独立，将重复计算

动态规划：可分为多个相关子问题，子问题的解被重复使用，子问题只求解一次，结果保存在表中，以后用到时直接存取

动态规划问题一般自底向上求解，不涉及到递归，而分治法一般自顶向下求解，涉及递归。动态规划可以求解的问题一般都会让你求一个最优解，而分治求解的问题一般不会这样。

当求解最优化问题时，如果经过证明得到由局部最优可以得到全局最优，那么可以使用贪心来求解；否则需要使用动态规划求解。

问题一般采用动态规划法，当具有：

1）最优子结构性质时：当一个问题的最优解包含了子问题的最优解时，称这个问题具有最优子结构

2）高度重复性：在问题的求解过程中，很多子问题的解将被多次使用

步骤

  1. 刻画一个最优解得结构特征

  2. 递归地定义最优解的值

  3. 计算最优解的值，通常采用自底向上的方法

  4. 利用计算出的信息构造一个最优解

这里自底向上也可以改成自顶向下构造表法，即在递归地过程中计算子问题，若子问题的结果在表中出现则直接使用不用计算，否则计算后更新表。

适用动态规划思想的算法：矩阵连乘、钢条切割、最长公共子序列、最优二叉搜索树、流水作业调度、0/1背包问题等。

重点是定义状态及状态转移方程。

矩阵连乘示例讲解

1、暴力方式：以分治的思想求解，但子问题并不是相互独立的，会导致子问题重复计算，时间复杂度升高。
暴力矩阵连乘算法图

图6：暴力矩阵连乘算法图

2、动态规划方式 以计算下面A1A2A3*A4为例： 矩阵连乘示例

图7：矩阵连乘示例

递推方程：
矩阵连乘递推方程

图8：矩阵连乘递推方程

下面是矩阵连乘的伪代码：
矩阵连乘伪代码

图9：矩阵连乘伪代码

以图7中的矩阵示例为例解释上述伪代码，输入矩阵为：
P[10(代表第一个矩阵的行), 20(代表第一个矩阵的列，第二个矩阵的行。后面依次类推), 50, 1, 100]。

m是一个二维矩阵，m[i,j]代表从第i个矩阵连乘到第j个矩阵所需的开销，上面示例中m需声明为m[5,4],其中m二维矩阵的第一行并没有被使用。

最终结果存储在m[1,4]中。二维数组s[i,j]存储的值是从第i个矩阵连乘到第j个矩阵所需的开销最小时的划分位置，比如s[1,4]值为2，就代表要使从第1个矩阵连乘到第4个矩阵所需的开销最小，就需要先计算m[1,2],再计算m[3,4],再将其二者相乘。

上述伪代码迭代计算顺序如下：

当R=2时，先迭代计算出：

m[1:2]=m[1:1]+m[2:2}+p[0]*p[1]*p[2]；

m[2:3]=m[2:2]+m[3:3]+p[1]*p[2]*p[3];

m[3:4]=m[3:3]+m[4][4]+p[2]*p[3]*p[4];

m[4:5]=m[4:4]+m[5][5]+p[3]*p[4]*p[5];

m[5:6]=m[5][5]+m[6][6]+p[4]*p[5]*p[6]的值；

当R=3时，迭代计算出：

m[1:3]=min(m[1:1]+m[2:3]+p[0]*p[1]*p[3],m[1:2]+m[3:3]+p[0]*p[2]*p[3]);

m[2:4]=min(m[2:2]+m[3:4]+p[1]*p[2]*p[4],m[2:3]+m[4:4]+p[1]*p[3]*p[4]);

......

m[4:6]=min(m[4:4]+m[5:6]+p[3]*p[4]*p[6],m[4:5]+m[6:6]+p[3]*p[5]*p[6]);

......

依次类推，根据之前计算的m值，迭代计算最优解。此方法会将每个子问题仅计算一遍，消除了重复计算。

为什么这里矩阵连乘选择DP而不是贪心，是因为贪心中的局部最优并不能得到全局最优，比如A52,B2100,C100*6,贪心第一步在AB或者BC中进行选择，由于计算AB开销1000小于计算BC开销1200，所以按照贪心算法计算结果应该是((AB)C)=4000,按照动态规划是(A(BC))=1260,不能证明贪心选择是全局最优解。

LCS(最长公共子序列)示例讲解

如<B,C,D,B>是X=<A,B,C,B,D,A,B>的子序列。

给定两个序列X和Y,如果Z既是X的子序列，也是Y的子序列，我们称它是X和Y的公共子序列。

LCS问题：给定两个序列，求X和Y长度最长的公共子序列。

暴力法：把一个序列中所有可能存在的子序列列出来(2^m,m为序列长度)，在另一个序列中查找是否存在此子序列(每次查找时间复杂度为O(n)),最终时间复杂度为O(n*2^m)。

动态规划方法：首先说明为何此题可使用动态规划方式来解决

Xi=﹤x1，⋯，xi﹥即X序列的前i个字符 (1≤i≤m)（前缀） Yj=﹤y1，⋯，yj﹥即Y序列的前j个字符 (1≤j≤n)（前缀）

假定Z=﹤z1，⋯，zk﹥∈LCS(X , Y)。

  • 若Xm = Yn (最后一个字符相同)，则不难用反证法证明：该字符必定是X与Y的任一最长公共子序列（设其长度为k）的最后一个字符，即是：Zk = Xm = Yn。这就得到：Zk - 1 ∈ LCS(Xm-1 , Yn-1)，即Z的前缀Zk-1是Xm-1 与 Ym-1 的最长公共子序列。这样就将问题缩小了，并且可以根据这个递推不断往回：Xm-1 与 Yn-1 的LCS。( LCS(X,Y) 的长度等于LCS(Xm-1,Yn-1) 的长度+1 ）
  • 若Xm ≠ Yn，则不难用反证法证明：要么Z ∈ LCS(Xm-1,Y)，要么Z ∈ LCS(X,Yn-1)。由于Zk ≠ Xm 与 Zk ≠ Yn中，至少有一个必然成立，若Zx ≠ Xm则有 Z ∈ LCS(Xm-1,Y) ，类似的，若Zk ≠ Yn，则有Z ∈ LCS(X,Yn-1)。此时，问题转换成求Xm-1 与 Y的LCS，以及 X 与 Yn-1的LCS。LCS(X,Y) 的长度为：max( LCS(Xm-1 , Y) , LCS(X , Yn-1) )。 由于上述当Xm ≠ Yn的情况中，求LCS(Xm-1 , Y) 的长度与LCS(X , Yn-1)的长度，这两个问题不是相互独立的：两者都需要求LCS(Xm-1 , Yn-1)的长度。另外两个序列的LCS中包含了两个序列的前缀的LCS，到这里得出结论：问题具有最优子结构性质，考虑用动态规划法。

也就是说，解决这个LCS问题，你要求三个方面的东西：

  1. LCS ( Xm-1，Yn-1 ) +1；
  2. LCS ( Xm-1，Y )，LCS ( X，Yn-1 )；
  3. max ( LCS( Xm-1，Y ) ，LCS( X，Yn-1) ) 如下图所示：
    状态c[i,j]代表序列x从0到i，序列y从0到j的两个子序列的最长公共子序列的长度，则有状态转移方程：
    LCS状态转移方程
图10：LCS状态转移方程

示例：
str1 : B D C A B A 长度为m = 6
str2 : A B C B D A B 长度为n = 7 找出这两个字符串中的最长公共子序列

  1. 首先，我们申请一个二维数组dp[m] [n]，用来存储两个str分别从1～m与1～n的所有长度的串对应的最长公共子序列的长度。
  2. 初始化一些已知的情况，比如：dp[0] [0] = 0，dp[i] [0] = dp[0] [j]，显而易见，当一个str长度为0，另一个长度无论你为多少，都没有公共子串，长度也就为0.
  3. 之后的值就取决于如上图中的另外两种情况，当str1[i] = str2[j] 的时候，就考虑对角上的前一个元素，在它的基础上+1，得到当前最大，当前元素的前一个对角元素是str1和str2长度都减去1的最优解（我们从开始就是这么定义的，相等在加1，不等就沿用左或上的最优，因为没有加1，那就找各自在对方不变的情况下回退一步的最优（一个长度减1，一个长度不变），即是最优）；；在不等的时候，只需要沿用上一次比较中str1[i-1] [j] 和 str2[i] [j-1]中比较大的一个，意思就是保留之前子串比较中最优的那一个，因为还没有得到最新的最优嘛（不能+1）。那么无论怎么样，我们都得到了当前的最优结果，供下一次再来选择比较。

具体的过程如图下： LCS演示示例图

图10：LCS演示示例图

最长上升子序列

dp(i)表示前i个序列中的上升子序列最长长度，递推公式为：dp(i)=max(dp(i),dp(j)+1) ifj<i,A[j]<A[i]

01背包问题

具体可参考文章:0-1背包问题的动态规划实现

哈希表

哈希表解决哈希冲突的方式：

  • 链表法：
  • 开放寻址法：在开放寻址法中，当要插入一个元素时，可以连续地检查散列表的个各项，直到找到一个空槽来放置这个元素为止。检查顺序可以是线性探测的，可以是二次探测(相比于线性探测只不过是探测下一个位置的函数不同)的，也可以是再次散列的。

全域哈希

哈希的根本缺陷：对于任意哈希函数而言，都存在一个不好的健集，使得所有的健都会哈希到同一个槽里去，那么如何解决这种情况呢？如何防止对某个键集永远有较差的表现？如何防止竞争对手使用这个键集来降低你的性能表现？ 一个词解决这个问题 —— random！

全域哈希的方法就是随机选择一个哈希函数H（当然不是每次操作都选择一个哈希函数，而是构建一个哈希表的时候随机选一个，选定之后这个哈希表的所有操作都是基于这个哈希函数，这种方法可以防止竞争对手别有用心的设计一个键集，同时也能避免某些键集永远会导致较差的性能，如果是，那么重新建一个表就行！）

贪心

最小生成树、迪杰斯特拉单源最短路径、哈夫曼编码、活动选择、任务调度、部分背包

证明贪心算法成立通常采用反证法。

最小生成树：具体可参考最小生成树-Prim算法和Kruskal算法

哈夫曼： 哈夫曼树定义：一颗有n个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树称作最优二叉树或赫夫曼树。

哈夫曼编码：示意图 哈夫曼编码示例图

图11：哈夫曼编码示例图

哈夫曼编码的意义在于可以使得任意一个字符的编码都不是另一个字符的编码的前缀，这种编码称作前缀编码。

具体可参考huffman编码——原理与实现

最短路径

对于所有边权值相同的连通图，图有向无向均可，可以使用BFS方法求解。

迪杰斯特拉（贪心）：适用于连通图，图有向无向均可，有环无环也不影响；前提是所有边权值为正，即不存在负权值的边。
具体可参考Dijkstra算法(一)之 C语言详解

Bellman-Ford最短路径算法，与迪杰斯特拉算法作用相同，也是求某个顶点到其它所有顶点之间的最短路径，不同之处在于Bellman-Ford可以应用于带有负权重边的图形，那么迪杰斯特拉算法相比Bellman-Ford的优势在哪呢？？？答：一个实现的很好的 Dijkstra 算法比 Bellman-Ford 算法的运行时间要低。

Bellman-Ford算法可以求含负权的单源点有向图(无向图可以看成是特殊的有向图)的最短路径，而且Bellman-Ford算法还可以用于判断图中是否存在负权回路（负权回路即是图中存在一个环，环上的所有权值之和是负数，那么这个环就是负权回路）。但存在负权回路的图是不能够求最短路径的，因为求最短路径时会在负权回路上不断地兜圈子，所有的最短路径长度会任意小。

Bellman-Ford算法执行过程：
Bellman-Ford算法遍历时如果每次起点权重+边权重<终点权重，则令终点权重=起点权重+边权重；最多遍历边数-1次；如果下一次遍历结果发现与上次遍历结果相同，则证明已经得到了最优解，可退出算法。退出之后还要检测是否出现了负环，检测方法为根据上述边的遍历顺序遍历一次，如果出现了终点权重>起点权重+边权重，则证明出现了负环。

求图中所有顶点之间的最短路径：

  • bellman-ford算法执行n次
  • 基于边的动态规划Matrix Mult
  • 基于顶点的动态规划Floyd-Warshall
  • 基于Bellman-Ford的一次计算结果重新定义权重后使用johnson算法

基于边的动态规划Matrix Mult： 对于i、j之间的最短路径，这条最短路径至多包含m条边，用L(i,j,m)表示从i到j，至多包含m条边的任何路径的权值最小值。当m=0时，i = j。因此当i=j时，L(i,j,0) = 0，否则L(i,j,0)=正无穷。对于m非0情况，我们可以发现，至多包含m条边时的最短路径，要么是最多包含m-1条边的最短路径，要么是在m-1条边的最短路径的基础上计算出在m条边下的最短路径（这里用例子说明，假如L(i,j,m)不是L(i,j,m-1)，则一定是走了一条i~>k -> j的路径，根据最优子结构，i~>k的路径一定是最短路径，这在推导m-1时已经得到了，因此i~>k的权值L(i,k,m-1)+w(k,j)就是L(i,j,m)。用递归式表达即L(i,j,m) = min{ L(i,k,m-1) + w(k,j) }, k from 1 to n。这个式子包含了L(i,j,m)=L(i,j,m-1)的情况，因为w(j,j)=0。因为图G=(V,E)的任一最短路径至多只能包含|V|-1条边，因此L(i,j,|V|-1)就是任意i到j的最短路径的权值。

递推公式：
L(i,j,m) = min{ L(i,k,m-1) + w(k,j) }, k from 1 to n

初始化：
L(i,j) = 0 (i = j时)
L(i,j) = 正无穷 (i != j时)
w(k,j)为权重矩阵

for m <- 1 to n-1
  do for i <- 1 to n
    do for j <- 1 to n 
      do for k <- 1 to n
        do if l(i,j) > l(i,k) + w(k,j)
          then l(i,j) <- l(i,k) + w(k,j)

基于顶点的动态规划Floyd-Warshall： 如果存在负环，假设点v在负环上，dis[v][v] 经过这条负环获得的距离小于0（dis[v][v]的初始值），会被更新为负值。因此通过判断每个节点自己到自己的距离是否有负值就可以判断负环了。

具体参考：Floyd算法(二)之 C++详解

Johnson算法 Johnson算法可以计算出两点之间最短路径经过了哪些顶点，具体路径长度的计算还要根据这些顶点在原图(转换前含负值的图)上计算。 具体参考：Johnson 全源最短路径算法

最小费用最大流

具体参考：最大网络流问题

算法一：一条途径是先用最大流算法算出最大流(不仅一条路径)，然后根据边费用，检查是否有可能在流量平衡的前提下通过调整边流量，使总费用得以减少？只要有这个可能，就进行这样的调整。调整后，得到一个新的最大流。

第二种情况是在寻找最大流的过程中就使用贪心保持费用最小，从而使得找出来的最大流路径就是最小费用的最大流。

NP问题

具体参考： [算法导论之P、NP、NPC问题][https://blog.csdn.net/bcb5202/article/details/51202589]

CATALOG
    FEATURED TAGS
    数据结构 Java基础 JDK源码阅读 Spring Web杂记 操作系统 协议 数据库 并发 消息中间件 产品 算法 MyBatis