程序 = 数据结构 + 算法

算法的效率度量

时间复杂度（Time complexity）

算法的时间复杂度是一个函数，它定性描述该算法的运行时间，时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数，使用这种方式时，时间复杂度可被称为是渐近的（渐近分析（asymptotic analysis、asymptotics），在数学分析中是一种描述函数在极限附近的行为的方法）。
例如，如果一个算法对于任何大小为n（必须比n0大）的输入，它至多需要$5n^{3}+3n$的时间运行完毕（也就是时间开销和问题规模n的关系为：$T_{(n)}=5n^{3}+3n$，这个时候，低阶项3n应该被抛弃，首项系数5也不保留），那么它的渐近时间复杂度是$O(n^{3})$；某个算法的运行时间至多需要$n^{2}+3n+1000$，那么其时间复杂度为$O(n^{2})$。

渐近规则：

多项相加，只保留最高阶的项，且系数变为1；
多项相乘，都保留。

阶数由低到高如下：

上图从左到右的算法中，随着问题规模的增大，时间开销会依次递增。

BOILERPLATE:

void test(int n){// n为问题规模
    int i = 1; // 只运算1次
    while(i<=n){ // 总共会运算n+1次
        i++;     // 总共会运算n次
        doSomething(i);  // 总共会运算n次
    }
    doMore(i);   // 只运算1次
}

这个算法的时间开销与问题规模n关系如下：
$T(n)=3n+3$
换算成渐近的时间复杂度就是O(n)。
如果在while循环里面增加一个for循环：

void test(int n){// n为问题规模
    int i = 1; // 只运算1次
    while(i<=n){ // 总共会运算n+1次
        i++;     // 总共会运算n次
        doSomething(i);  // 总共会运算n次
        for(int j = 0; j < n; j++){ // 共总会运算n次
            doSomething(j);
        }
    }
    doMore(i);   // 只运算1次
}

这个算法的时间开销与问题规模n关系如下：
$T(n)=O(n)+O(n^{2})$
换算成渐近的时间复杂度就是$O(n^{2})$（去掉低阶项）。

如果有多层嵌套循环，只需关注最深层循环循环了几次。

查找（Search）

leetcode二分查找专题

顺序查找

顺序查找又称现行查找，主要用于在线性表中进行查找，序列有序无序皆可。

对无序线性表进行顺序查找，查找失败时要遍历整个线性表。
对有序线性表进行顺序查找，查找失败时不一定要遍历整个线性表。

折半查找

折半查找又称二分查找，仅适用于有序的顺序表。

BOILERPLATE:

// 重点在于low和high的摇摆切换
public int BS(int[] arr, int key) {
    int low = 0;
    int high = arr.length - 1;
    int half;
    while (low <= high) {
        half = (low + high) / 2;
        if (arr[half] == key) {
            return half;
        } else if (arr[half] > key) {
            high = half - 1;
        } else {
            low = half + 1;
        }
    }
    return -1;
}

分块查找

排序

内部排序指在排序期间元素全部存放在内存中的排序。
外部排序指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间进行移动。

插入排序

直接插入排序

折半（二分）插入排序

交换排序

冒泡排序

快速排序

选择排序

简单选择排序

堆排序

归并排序

基数排序

贪心算法（贪婪算法/Greedy Algorithm）

维基百科

在对问题求解时，总是做出在当前看来是最好的选择。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种子问题最优解成为最优子结构。
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。

动态规划（Dynamic programming/DP）