第一课

1.0 认识时间复杂度、额外空间复杂度

　　常数时间的操作：一个操作如果和数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。
　　时间复杂度为一个算法流程中，常数操作数量的指标。常用O（读作big O）来表示。具体来说，在常数操作数量的表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果记为f(N)，那么时间复杂度为O(f(N))。
　　评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是常数项时间。

　　额外空间复杂度：在执行代码过程中申请的额外存储空间，比如变量，有限个变量则O（1），分析额外空间复杂度和时间复杂度类似;如使用冒泡排序对一个数组排序，期间只需要一个临时变量temp，那么该算法的额外空间复杂度为O(1)。又如归并排序，在排序过程中需要创建一个与样本数组相同大小的辅助数组，尽管在排序过后该数组被销毁，但该算法的额外空间复杂度为O(n)。

　　题目：一个有序数组A，另一个无序数组B，请打印B中的所有不在A中的数，A数组长度为N，B数组长度为M。
       思路1(遍历查找)：对于数组B中的每一个数，都在A中通过遍历的方式找一下；复杂度分析：遍历B[0,M-1],遍历A[0,N-1],故O(M*N)时间
       思路2(二分查找):对于数组B中的每一个数，都在A中通过二分的方式找一下;
       思路3(类似外排):先把数组B排序，然后用类似外排的方式打印所有在A中出现的数；

　　先看第一步，排序，数组B使用二分排序，时间复杂度为O(M*log2(M))
　　再看第二步，数组B排序完成之后，数组A和B就都是有序的了，我们假设一个a指针，指向数组A第一个元素，再假设一个数组b指向数组B第一个元素，然后两个指针想对应的数字进行比较，然后根据比较　　大小，进行指针之间的移动。
　　a指针移动的条件是，a指针指向的数字<b指针指向的数字时，向右移动一位。
　　b指针移动的条件是，b指针指向的数字<=a指针指针指向的数字，如果=只向右移动，不打印，如果<，打印数字，且移动。

　循环往复以上步骤即可，当指针a和指针b任意一个指针走到尽头，就意味着程序的中止，我们假设最坏情况，同时到最后才结束，那么他的时间复杂度为0(N+M)

　再加上之前排序的时间复杂度，最终复杂度为O(M*log2(M))+O(N+M)

1.1 对数器

步骤：有一个你想要测的方法a；实现一个绝对正确但是复杂度不好的方法b；实现一个随机样本产生器；实现比对的方法；把方法a和方法b比对很多次来验证方法a是否正确；如果有一个样本使得比对出错，打印样本分析是哪个方法出错；当样本数量很多时比对测试依然正确，可以确定方法a已经正确。

1.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);
                }
            }
        }
    }

View Code

插入

public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        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);
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

View Code