数据结构与算法之美笔记

是什么：

数据结构是用来存储数据的一组数据结构，算法是用来操作数据的一组方法，他们相辅相成。数据结构是为算法服务的，算法作用于特定的数据结构上的。

学什么：

• 效率和资源消耗的度量衡：复杂度分析
• 最常用和最基础的20个数据结构和算法，学习它们的来历，特点，合适解决什么问题和实际应用场景。
• 数据结构：数组，链表，栈，队列，散列表，二叉树，堆，跳表，图，Tire树
• 算法：递归，排序，二分查找，搜索，哈希算法，贪心算法，分治算法，回溯算法，动态规划，字符串匹配算法

怎么学：

• 每周把这些数据结构和算法自己实现，多思考，多询问，每篇写笔记，我主要使用Java来实现。

为什么需要复杂度分析：

• 不同的环境造成的测试结果差异大
• 数据的规模会影响结果(规模太小无法，测试结果无法反应算法的性能)

复杂度：

• 复杂度是算法执行时间(或占用空间)与数据规模的增长关系
• 复杂度分析又分为时间复杂度和空间复杂度，用大O来表示
• 时间复杂度表示方法T(n) = O(f(n)),其中T(n)表示执行的总时间，n表示数据规模的大小，f(n)表示每行代码执行的次数总和。该方法的由来就是所有代码执行时间T(n)与每行代码执行次数n成正比。

如何看时间复杂度：

• 只关注循环中次数最多的代码。例如，58行的执行次数为1，59和60的执行次数为n，所以f(n)=1+2n,所以T(n)=O(2n+1)=O(n)

  
  image.png
• 加法法则：总复杂度等于量级最大的那段代码的复杂度,其中第一段与n无关O(1),第二段为O(n),第三段为O(n^2),综合这三段代码的时间复杂度，我们取其中最大的量级。所以，整段代码的时间复杂度就为O(n )。

    int cal(int n) {
        int sum_1 = 0;
        for (int i = 1; i < 100; i++) {
            sum_1 = sum_1 + i;
        }


        int sum_2 = 0;
        for (int i = 1; i <= n; i++) {
            sum_2 = sum_2 + i;
        }


        int sum_3 = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; i <= n; j++) {
                sum_3 = sum_3 + i * j;
            }
        }
        return sum_1 + sum_2 + sum_3;
    }

• 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积,在O(n)的代码段里调用O(n)的代码段，所以cal的时间复杂度为O(n^2)，相当于嵌套循环。

    int cal(int n) {
        int sum_2 = 0;
        for (int i = 1; i <= n; i++) {
            sum_2 = sum_2 + f(i);
        }
        return sum_2;
    }


    int f(int n) {
        int sum_3 = 0;
        for (int i = 1; i <= n; i++) {
            sum_3 = sum_3 + i;
        }
        return sum_3;
    }

常见的时间复杂度

• 非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括，O(2^n)（指数阶）、O(n!)（阶乘阶）
• 随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括，O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^{2)（平方阶）、O(n}3)（立方阶）

O(logn)和O(nlogn)

• 想知道这段代码的时间复杂度，首先执行次数最多是 i = i * 2;i每次都比之前大一倍相当于
  2^0 2^1 2^2 2^3 2^4....2x = n相当于一个等比数列,x即为该段代码执行的次数，x=log2n，所以，这段代码的时间复杂度就是O(log2n)。
• 同样把2换成3时间复杂度就是O(log3n),但是log3n=log32*log2n，log32是常数，所以也是O(log2n),最后都记为O(logn)。

     void cal(int n) {
        int i = 1;
        while (i <= n) {
            i = i * 2;
        }
    }

• 而O(nlogn)就是前面的乘法法则，如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn)。

O(m+n)和O(m*n) ：

• 当数据规模无法评估哪个较大时，加法法则失效，可以使用 O（m+n）的方式。

    int f(int n, int m) {
        int sum_1 = 0;
        for (int i = 1; i <= n; i++) {
            sum_1 = sum_1 + i;
        }

        int sum_2 = 0;
        for (int i = 1; i <= m; i++) {
            sum_2 = sum_2 + i;
        }
        return sum_2 + sum_1;
    }

空间复杂度

比较简单，表示算法的存储空间与数据规模之间的增长关系。

int[] a = new int[n];

同一个算法，在不同的情况时间复杂度也会不同，例如在数组中查找一个数据，可以遍历整个数组,这时候该代码的时间复杂度为O(n)

    int find(int[] a, int x) {
        int res = -1;
        for (int i = 0; i < a.length; i++) {
            if (x == a[i]) res = 0;
        }
        return res;
    }

但是我们并不需要遍历整个数组，只要找到返回就行了,只是加句break。

    int find(int[] a, int x) {
        int res = -1;
        for (int i = 0; i < a.length; i++) {
            if (x == a[i]) {
                res = 0;
                break;
            }
        }
        return res;
    }

这时候它的复杂度是不确定的，例如第一个O(1)就找到或者最后一个才找到O(n)，其中O(1)是该算法的最好情况时间复杂度，O(n)是该算法的最坏情况时间复杂度。
同样，还有一个平均时间复杂度，其实数据在数组中的位置有n+1种情况，在数组的 0～n-1 位置中和不在数组中，我们把在每种情况需要查找的次数相加然后除以n+1，这时候就可以得到需要遍历元素个数的平均值
1+2+3+4.....+n+n/n+1 = n(n+3)/2(n+1)
这时候平均时间复杂度为O(n)。