算法

本篇博客参考《算法图解》(真是一本神书)，并加入了一些自己的想法。

算法的五个特性：

（1）输入：可以有0个入参

（2）输出：至少有1个输出

（3）确定性

（4）可行性

（5）有穷性

算法的运行时间业界普遍采用大O表示法：

常见的大O运行时间:

O(n) 也叫线性时间，像简单查找

O(logn) 也叫对数时间，像二分查找

O(n * logn) 一种较快的排序方法，像快速排序

O(n^2) 一种较慢的排序方法（并不完全是 n * n，第一次需要检查n个元素，随后依次为n-1,n-2 因此是 O(n * 1/2 *n)，但大O表示法省略1/2这些常数）

O(n!) 一种非常慢的方法，案例是旅行商问题

注：算法运行时间是以其增速的角度度量的，大O表示法指出了最糟情况下的运行时间，比如说简单查找(最笨的方法挨着找一边)的运行时间总是为O(n)

常见的算法(并有带上自己的小demo)：

（1）快速排序算法

快速排序的最差时间复杂度和冒泡排序是一样的都是 O(N2)，它的平均时间复杂度为 O(NlogN)。

（2）选择排序（冒泡排序，循环次数两者一样，但是交换次数前者比后者要少）

    // Selection sort 选择排序 时间复杂度 O(n^2)
    private void selectionSort() throws Exception {
        int[] arrs = new int[]{3,5,1,9,7,13,12};

        for (int i = 0; i < arrs.length; i++) {
            int temp = arrs[i];
            int flag = i;
            for (int j = i + 1; j < arrs.length; j++) {
                if (arrs[j] < temp) {
                    temp = arrs[j];
                    flag = j;
                }
            }
            if (flag != i) {
                arrs[flag] = arrs[i];
                arrs[i] = temp;
            }
        }
    }

// bubble sort 冒泡排序
    private void bubbleSort() throws Exception {
        int[] arrs = new int[]{3,5,1,9,7,13,12};
        for (int i = 0; i < arrs.length; i++) {
            for(int j = arrs.length - 1; j>=i; j--) {
                if(arrs[i] > arrs[j]) {
                    int temp = arrs[i];
                    arrs[i] = arrs[j];
                    arrs[j] = temp;
                }
            }
        }
    }

（3）归并排序

（4）二分查找算法

对于包含n个元素的列表，用二分查找最多需要 $log_2$ N步（2是下标位置。n的对数，对数就是 $a^x=b$ , $a,b>0$ 的解），而简单查找最多需要n步。

    // Binary Search (二分查找法 | 必须是有序的)
    // 本例子是查找某个数在数组中的位置，如果不存在则返回 -1
    private int binarySearch(int param) throws Exception {
        int[] arrs = new int[]{1,3,5,7,9,11,13};

        int low = 0;
        int high = arrs.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            int guess = arrs[mid];
            if(guess == param) {
                return mid;
            }
            if(guess > param) {
                high = mid - 1;
            }
            if(guess < param) {
                low = mid + 1;
            }
        }

        return -1;
    }

（5）BFPRT(线性查找算法)

（6）DFS（深度优先搜索）

（7）BFS(广度优先搜索)

广度优先搜索让你能够找出两样东西之间的最短距离，比如说国际跳棋最少走多少步就可获胜，根据你的人际关系找到关系最近的医生，双子峰到金门大桥的最短换乘公交。

了解图的概念，图由节点和边组成。

（8）狄克斯特拉算法

双子峰到金门大桥的最短换乘公交可使用广度优先搜索（非加权图中），如果是最短时间可以使用本算法（加权图中）。

该算法用于每条边都有关联数字的图，这些数字称为权重。带权重的图称为加权图，不带权重的图称为非加权图。

（9）Dijkstra算法

（10）朴素贝叶斯分类算法

（11）贪婪算法

　　每一步都选择局部最优解，最终得到的就是全局最优解。比如说背包问题偷东西的案例可能不太适应，但是有时候只需要找到能够大致解决问题的算法，此时贪婪算法正好可以派上用场。这里可能需要思考的是 Np问题

（12）动态规划算法

　　先解决子问题，再逐步解决大问题。每种动态规划解决方案都涉及网格。

（13）K最近邻算法

　　判断眼前的水果是橙子还是柚子，脑子里有个图表，横坐标是大小，纵坐标是颜色。创建推荐系统，预测股票市场也可以采用该算法。甚至是机器学习的最核心的部分也是基于此算法进行不断的训练。

其他

（1）搜索引擎的工作原理：利用了反向索引，将关键字与具体的网页建立散列表，如果搜索a，查看包含a的页面具体有几个展示给用户。

(2) 分布式算法MapReduce，如果数据表的行数超过数十亿后，处理起来将很吃力，这时可以通过Hadoop来使用MapReduce，该算法基于两个简单的理念：映射（map）和归并（reduce）函数。

（3）异或^ 运算：

相异为1，相同为0。0 ^ 任何数＝任何数，1 ^ 任何数 = 任何数取反