算法第一课

假设寻址操作代价为c；那么便利一个大小为n的数组，代价为nc,称复杂度为o(n);

若代价为（an^2+bn+k）* c，则复杂度为o(n^2)。

二分查找的复杂度o(logn)

复杂度例子

两个有序数组，A中N个元素，B中M个元素，寻找其中相同元素：

1. 遍历A中每一个元素，再在B中遍历寻找相同元素，复杂度O(m*n)
2. 遍历A中每一个元素，再在B中二分查找相同元素，复杂度O(n*log(m))
3. A、B设定两个指针，指向第一个元素，比较二者大小，谁小谁的指针向右移动，若相同同时移动A、B指针，则最差情况下指针移动了M+N的距离，复杂度O(N+M)

这三种情况复杂度分别为O(mn)、O(nlog(m))、O(N+M)，第一个肯定是最糟糕的，后面两种则要分情况讨论，并不能单纯的说第三种好，例如N=4、M=2^{32，第二种为O(4*42）、第三种为O(4+2}32)

空间复杂度

空间复杂度又称为额外空间复杂度，即为了完成目的所需要的额外的空间。不包括所给的原始空间和输出的空间。

例如一个数组

1 2 3 4 5 | 6 7

需要把“|”左右的交换

一种方法是可以定义一个新的数组，先把6 7放到左边，再放其他的，则需要额外空间7

另外一种方法是：

先对 1 2 3 4 5 在原地进行逆序，为5 4 3 2 1

再对 6 7 逆序，为 7 6

数组变为5 4 3 2 1 | 7 6

再整体逆序，5-6、4-7、3-1

数组变为6 7 | 1 2 3 4 5

则不需要辅助空间（辅助空间只需要交换一个数的，为O(1))。

最优解

在满足时间复杂度最小的情况下，考虑空间复杂度最小的解。

排序

冒泡排序

时间复杂度O(N^2)，额外空间复杂度O(1)，实现可以做到稳定性

6 5 1 2 4 3

开始：

5 6 

5 1 6

5 1 2 6

5 1 2 4 6

5 1 2 4 3 6

再将 剩下数 开始进行相同的操作，时间复杂度O(N^2)

public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int e = arr.length - 1; e > 0; e--) {
        for (int i = 0; i < e; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
            }
        }
    }
}

一个小技巧：对数器

如果想知道一个流程对不对，需要依赖OJ（Online Judge)，还可以依赖对数器。

准备一个容易写不出错的版本，生成随机数据，让两套流程去处理，如果数万次都相同，则可以认为流程正确。

例子：

一个容易写不出错的版本：

public static void comparator(int[] arr) {
    Arrays.sort(arr);//调用系统的排序方法
}

生成一个随机数组：

public static int[] generateRandomArray(int maxSize, int maxValue) {
//Math.random()生成double[0,1)
//(int) ((maxSize + 1) * Math.random())->[0,size]整数
//size = 6, size+1 = 7;
//Math.random()*7->double [0,7)
//int 后 [0,6]
    int[] arr = new int[(int) ((maxSize + 1) * Math.random())];//生成一个随机长度数组 
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
    }
    return arr;
}

测试：

//比较两个数组
public static boolean isEqual(int[] arr1, int[] arr2) {
    if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
        return false;
    }
    if (arr1 == null && arr2 == null) {
        return true;
    }
    if (arr1.length != arr2.length) {
        return false;
    }
    for (int i = 0; i < arr1.length; i++) {
        if (arr1[i] != arr2[i]) {
            return false;
        }
    }
    return true;
}

public static int[] copyArray(int[] arr) {
    if (arr == null) {
        return null;
    }
    int[] res = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        res[i] = arr[i];
    }
    return res;
}

//打印数组
public static void printArray(int[] arr) {
    if (arr == null) {
        return;
    }
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }
    System.out.println();
}

public static void main(String[] args) {
    int testTime = 500000;
    int maxSize = 100;
    int maxValue = 100;
    boolean succeed = true;
    for (int i = 0; i < testTime; i++) {
        int[] arr1 = generateRandomArray(maxSize, maxValue);
        int[] arr2 = copyArray(arr1);
        bubbleSort(arr1);
        comparator(arr2);
        if (!isEqual(arr1, arr2)) {
            succeed = false;
            break;
        }
    }
    System.out.println(succeed ? "Nice!" : "Fucking fucked!");

    int[] arr = generateRandomArray(maxSize, maxValue);
    printArray(arr);
    bubbleSort(arr);
    printArray(arr);
}

对数器的另一个应用：贪心算法

比如在0点到20点有许多课，需要安排课尽量的多。

贪心策略有几种方法，但不知道哪种对

先按哪个课早安排哪个

或

先按哪个课短安排哪个

或

先按哪个更早结束安排哪个（正确的）

如果不知道哪个是对的，自己可以用对数器测试哪种是正确的方法。

选择排序

时间复杂度O(N^2)，额外空间复杂度O(1)，实现可以做到稳定性

就是选最小的放在第一个，第二小的放在第二个...

public static void selectionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            //查找最小的
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        swap(arr, i, minIndex);
    }
}

插入排序

时间复杂度O(N^2)，额外空间复杂度O(1)，实现可以做到稳定性

6 3 2 4

3 6 //插入3，3比6小，交换

3 2 6 //插入2，2比6小，交换

2 3 6 //2比3小，交换

2 3 4 6 //插入4,4比6小，交换

类似于扑克牌整理牌，每次插入到应该的位置。

最好情况完全顺序 O(N)，最坏情况完全逆序 O(N^2)

public static void insertionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    //i从前往后，表示插入的元素；j从后往前，不断比较，找到插入的位置
    for (int i = 1; i < arr.length; i++) {
        for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
            swap(arr, j, j + 1);
        }
    }
}

三大排序

	归并排序	快速排序	堆排序
时间复杂度	O(N*logN)	O(N*logN)	O(N*logN)
空间复杂度	O(N)	O(logN)	O(1)

归并排序

实际是递归，在递归过程中，把父函数压到栈中，再去调用子函数

归并排序就是先把左边部分排好，再把右边部分排好

public static void mergeSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    mergeSort(arr, 0, arr.length - 1);
}

public static void mergeSort(int[] arr, int l, int r) {
    if (l == r) {
        return;
    }
    int mid = l + ((r - l) >> 1);//>>>高位补0的右移，>>高位补符号位的右移，右移的运算速度比直接除2更快
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    merge(arr, l, mid, r);//每个子方法都调用了这个方法，通过它进行了数的交换
}

再进行两个有序数组的排序，

左边右边分别设定两个指针，指向第一个元素，比较二者大小，谁小谁的指针向右移动，把小的放到一个新的数组help去

public static void merge(int[] arr, int l, int m, int r) {
    int[] help = new int[r - l + 1];
    int i = 0;
    int p1 = l;
    int p2 = m + 1;
    while (p1 <= m && p2 <= r) {
        help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= m) {
        help[i++] = arr[p1++];
    }
    while (p2 <= r) {
        help[i++] = arr[p2++];
    }
    for (i = 0; i < help.length; i++) {
        arr[l + i] = help[i];
    }
}

过程

5 3 4 6 7 2 9 3 

左边：

    5 3 4 6
    
        左边 5 3 
        
            左边：对5排序，直接RETURN
            
            右边：对3排序，直接RETURN
            
            合并：变成3 5

        右边 4 6

            左边：对5排序，直接RETURN
            
            右边：对3排序，直接RETURN

            合并：变成4 6

        合并：变成 3 4 5 6

右边：

    略

        2 3 7 9

合并：变成 2 3 3 4 5 6 7 9

算法复杂度：

时间复杂度：

T(N) = T(N/2) + T(N/2) + O(N) = 2T(N/2) + O(N)

T为递归过程的复杂度，O(N)为合并的复杂度

使用MASTER公式进行估计。

T(N) = aT(N/b) + O(N^d)

使用Master公式可得，其复杂度为O(Nlogn)

Master公式

关于Master公式的补充可参考：
Master公式的补充