时间复杂度

一个和数据量有关，只要高阶项，不要低阶项，不要常数项的操作次数表达式（类似于求当n趋向于∞时，该多项式等价于什么）

三种排序算法的时间复杂度

选择排序

    // 选择排序
    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int minIndex, i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

从选择排序的过程分析，执行次数为1+2+3+......+n-1，因此时间复杂度为O（n²）
也可以从代码来分析，外层for循环执行次数的级别为n，内层for循环执行次数的级别也为n，所以时间复杂度为O（n²）。

冒泡排序

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

从冒泡排序的过程分析，执行次数为1+2+3+......+n-1，因此时间复杂度为O（n²）
同样可以从代码来分析，外层for循环执行次数级别为n，内层for循环执行次数的级别也为n，所以时间复杂度为O（n²）。

插入排序

    // 插入排序
    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {//如果数组中只有0个或1个元素，则不需要排序
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                //若新来的数大于左边的数，则将其不断左移，直到0~i范围内也有序
                swap(arr, j, j + 1);
            }
        }
    }

插入排序的情况特殊一些，它的时间复杂度和待排序数组的状态有关，
当待排序数组为倒序时，每次插入新的数都要调整已经有序数组的状态，故执行次数为1+2+3+......+n-1，即时间复杂度为O（n²）
从代码来分析，外层for循环执行次数的级别为n，内层for循环执行次数的级别为n，故时间复杂度为O（n²）。
当待排序数组有序时，每次新插入数不需调整有序数组，故执行次数为n，时间复杂度为O（n）
从代码来分析，新插入数不满足第二个for循环的条件，因此只有第一个for循环会执行，故时间复杂度为O（n）。

对于严格固定流程的算法，比如插入排序，我们通常考虑其最差的时间复杂度，因此插入排序的时间复杂度为O（n²）。
而对于流程中存在随机行为的算法，我们则需考虑平均或者期望的时间复杂度。

同时上面的分析也给我们一个其实，不要根据代码结构来判断时间复杂度，例如插入排序有两个for循环，在最好情况下，时间复杂度却是O（n）。再比如下面的代码：

        int N = 200000;
        long start;
        long end;
        System.out.println("测试开始");
        start = System.currentTimeMillis();
        for (int i = 1; i <= N; i++) {
            for (int j = i; j <= N; j += i) {
            // 这两个嵌套for循环的流程，时间复杂度为O(N * logN)
            // 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + ... + 1/n，也叫"调和级数"，数量级为O(logN)
            // 所以如果一个流程的表达式 : n/1 + n/2 + n/3 + ... + n/n
            // 那么这个流程时间复杂度O(N * logN)
            }
        }
        end = System.currentTimeMillis();
        System.out.println("测试结束，运行时间 : " + (end - start) + " 毫秒");

        System.out.println("测试开始");
        start = System.currentTimeMillis();
        for (int i = 1; i <= N; i++) {
            for (int j = i; j <= N; j++) {
                // 这两个嵌套for循环的流程，时间复杂度为O(N^2)
                // 很明显等差数列
            }
        }
        end = System.currentTimeMillis();
        System.out.println("测试结束，运行时间 : " + (end - start) + " 毫秒");

结果为：

测试开始
测试结束，运行时间 : 6 毫秒
测试开始
测试结束，运行时间 : 9623 毫秒

因此时间复杂度需要基于对算法流程的充分理解再加以分析才可得出。

空间复杂度

强调额外空间，并不包含入参或者出参的空间，指完成算法必须开辟的额外空间大小。

最优解

在时间复杂度最优的情况下，尽量少使用额外空间的解。