算法和数据结构

James 2020年03月10日 2次浏览

很多同学一问到数据结构或者说算法都会觉得很难，不好理解，那么今天我们就来好好学习它。

时间和空间复杂度

程序是用来解决问题的，而解决问题的思路或者方法有很多种，每一种方式方法都有它的好处与坏处，每种方法在时间和空间上的消耗不尽相同，所以我们只有了解了什么是时间和空间复杂的并且掌握如何
来评估某种方式方法在时间和空间上的复杂度过后我们才能衡量当前这种方式的优劣程度，最后进行比较，最终选择最优的实现方式来解决问题。

时间复杂度

时间复杂度推导原则：

  • 如果运行时间是常数量级，则用1表示
  • 只保留时间函数中最高阶项，例如：T(n)=0.5n2+0.5n中最高阶项是0.5n2
  • 如果最高阶项存在，则省去前面的系数
    常见的时间复杂度量有(通过从小到大顺序排列)：
  • O(1)：常量阶，运行时间为常量
  • O(logn)：对数阶，如二分查找法
  • O(n)：线性阶，如n个数内找最大值
  • O(nlogn)：对数阶，如快速排序算法
  • O(n^2)：平方阶，如选择排序，冒泡排序，需要双重循环
  • O(n^3)：立方阶，如两个n阶矩阵的乘法运算
  • O(2^n)：指数阶，如n个元素集合的所有子集的算法
  • O(n!)：阶乘阶，如n个元素全部排列的算法

空间复杂度

一个算法的存储量包含以下三种：

  • 程序本身所占用的空间
  • 调用某个算法函数的入参所占用的空间
  • 算法中的辅助变量所占用的空间
    输入数据所占用空间取决于问题本身，和算法无关，所以我们只需要分析算法中辅助变量所占用的额外空间。
    如果算法中所使用的辅助变量和问题规模n无关，则它的空间复杂度为O(1)
    注意：空间复杂度比时间复杂度分析要少。对于递归算法来说，代码通常较短，占用空间通常较少，空间复杂度较低；对于非递归算法来说，代码较长，占用空间较大，空间复杂度较高。

数组、链表、跳表

  • 数组在内存中开辟一块连续的内存空间，并在此空间中存放数据，数组的特点是读取较快，写入较慢。数组从头插入和从尾部插入的时间复杂度是O(1)，但是从指定下标开始插入，由于需要挪动后面的元素
    所有时间复杂度是O(n)，但是读取就很快了，直接通过下标就能直接返回，时间复杂度是O(1)
  • 链表可以分为单链表循环链表和双向链表，java中LinkedList就是一个标准的双向链表，特点是增删改比较快，读取较慢。链表的元素添加只需要将需要插入位置的前一个节点的next指针指向需要添加的元素上，
    然后将当前元素的next指针指向指向当前节点的节点原本的next地址。删除一个元素只需要将当前节点的前一个节点的next指针指向当前节点的next指针地址，查询需要从头节点开始一个一个往下找。
    链表的增删改在时间复杂度上是O(1)，但是查询的时间复杂度是O(n)
  • 跳表是为了优化链表的查询缺陷，实际上是一种空间换时间的思维方式。通过增加多级索引的方式来达到快速查找，索引的每一级是上一级索引的两倍2-4-8-16。跳表在时间复杂度上就是O(logn)，
    空间复杂度为O(n)

栈、队列

  • 栈的特点是先进后出，可以将栈看成是一个桶，先放的东西在下面，而我们只能从上面开始拿东西。一般用于有较强顺序相关性的场景（例如，编译器符号开闭语法检测），栈的操作只有两种，压入栈和弹出栈，
    且只能操作栈顶，只有栈顶元素是可访问的。栈的实现由两种，链表和数组。
  • 队列特点是先进先出，队列在生活中场景就是排队，队列一般由数组和链表实现。

哈希表

哈希表也称散列表，是将关键码（key）进行Hash得到表中一个位置（下标）来直接访问的，这个函数称为哈希函数。一个简单的hash函数是将一个字符串中的每一个字符的ASCII码加在一起得到hashcode然后在mod上
一个数（一般是表的长度）来得到它在表中的index，在java中有一个HashCode函数，不同的字符串通过哈希函数计算出来的结果有可能相同，这种现象我们称之为哈希碰撞，这种想象很常见，那么如果出现哈希碰撞
一般会怎么解决呢，在java中是通过新增了一个维度，也就是在相同的位置新增一个链表，这种方式称为拉链式解决冲突法，但是这种方式有个不好之处在于在查询数据的时候之前可以直接通过hash函数直接读取，
现在通过hash过后还需要在链表上便利，时间复杂度从O(1)升至O(n)，java中HashMap在JDK1.7是使用数据+链表实现，在JDK1.8以后，使用数组+链表+红黑树实现，在链表长度达到指定阈值（默认为8）时转为红黑树，
旨在优化HashMap的查询时间复杂度，从之前的O(n)提升至O(logn)。

二叉树

  • 二叉树：也就是他的儿子节点只有两个（左子树和右子树），且树的叶子节点不会指向父节点或者兄弟节点（没有环，有环的称为图）。
    树的遍历有三种，如下：
    1. 前序遍历：根-左-右
    2. 中序遍历：左-根-右
    3. 后序遍历：左-右-根
  • 满二叉树：一颗二叉树中所有节点要么没有子节点，要么左右子节点都有。一棵满二叉树树有多少个节点可以用公式n = (2^k)-1计算得出，其中n表示它的节点数，k表示它的深度。
  • 完全二叉树：完全二叉树是在满二叉树上延伸出来的，假设一棵树的深度为h，且除第h层以外的1~h-1是一颗满二叉树，并且第h层的所有节点都连续几种在左边，那么这就是一颗完全二叉树。
  • 二叉搜索树（二叉查找树）：在普通二叉树的基础上，各个节点的所有左子树的数据小于根节点，各个节点的所有右子树的数据大于根节点。

递归

先递进，再回归。函数直接或者间接的调用自身函数，那么我们称该函数为递归函数，递归方法有四个部分组成，递归终结、逻辑、递归到下一层、数据清理，常见案例有求N的阶乘或者斐波那契数列，代码模板：

public Objcet recur(Objcet... params) {
    //terminator
    if(prams...){
        return x;
    }
    
    //process current logic
    process(params);
    
    //drill down
    Objcet result = recur(params...);
    
    //restore current status
    
    return result;
}

分治和回溯

  • 分治：分治是将一个大的问题分解成多个规模较小的，且结构和原问题相似的子问题，递归计算这些小问题，最后将结果合并，就得到了原问题的结果。代码模板：
def divide_conquer(problem,param1,param2,……):
# resursion terminator
if problem is None:
    print_result
    return 
# prepare data
data = prepare_data(problem)
subproblems=split_problem(problem,data)

# conquer subproblems
subresult1 = self.divide_conquer(subpromblems[0],p1,……)
subresult2 = self.divide_conquer(subpromblems[1],p1,……)
subresult3 = self.divide_conquer(subpromblems[2],p1,……)
……
# process and generate the final result
result = process_result(subresult1,subresult2,subresult3,……)
  • 回溯：回溯采用分布试错的方式，它尝试分布的去解决某一个问题。它在通过尝试过后发现现有的答案不能得到正确的解答过后回到上一步或者上几步重新选择其他的分布进行计算。回溯相当于走迷宫，
    我们走迷宫的目标就是从迷宫中走出来，那么回溯求教就相当于是找出口，我们走到一个路口发现有多种选择，然后我们随便找一条路继续走，当我们走到该条路的尽头时发现没有路了，这个时候我们就会
    倒回去重新选择其他的路，直到走出迷宫。

深度优先(DFS)和广度优先(BFS)

深度优先和广度优先算法是针对图和树的查找或遍历算法

  • 深度优先遍历：顾名思义，也就是从根节点开始从左子树一直往树的最深处遍历，直到没有子节点再找该节点的根节点的右子树继续使用深度优先算法遍历，代码模板：
class Test{
    public void dfs(TreeNode node) {
        if(node==null){
            return;
        }
        System.out.println(node);
        if(node.left!=null){
            dfs(node.left);
        }
        if(node.right!=null){
            dfs(node.right);
        }
    }
}
  • 广度优先遍历：广度优先也就是从根节点开始下面一层一层的遍历，想水波纹一样往下扩散，在每一层中从左向右（也可以从右向左）依次访问，访问完这一层过后访问下一层，直到没有节点可以访问，代码模板：
class Test {
    public void bfs(TreeNode node){
        Queue<TreeNode> queue = new ArrayQueue<>();
        if(node==null){
            return;
        }
        queue.add(node);
        while(!queue.isEmpty()){
            //从队列中获取节点并删除
            TreeNode treeNode = queue.remove();
            if(treeNode.left!=null){
                queue.add(treeNode.left);
            }
            if(treeNode.right!=null){
                queue.add(treeNode.right);
            }
            System.out.println(treeNode);
        }
    }
}

贪心算法

贪心算法旨在每次选择都采取局部最优解，从来理想达到全局最优解，他和动态规划的区别在于，贪心算法的每次选择都是局部最优的，且不能回退，而动态规划则会保存之前的结果，并根据之前的结果
和当前的结果进行对比，然后选择，是支持回退的。如果一个问题可以通过贪心算法解决，那么贪心算法一般是解决该问题的最好办法。
适用场景：一个问题可以分解成多个子问题，而各个子问题的优劣可以决定全局的优劣。

二分查找

二分查找也叫折半查找，旨在每次查找时取表中元素最中间位置（长度/2）和需要查找的元素进行比较，如果相等，说明已经找到，直接返回，如果大于或者小于根据排序规则选择向左还是向右继续查找。
该算法必须要求表中元素必须是有序排列的。例如：现在有一个1-100的有序（从小到大升序）的数组，需要从中找出一个元素（比如70），问使用二分查找算法需要找几次。首先取数组中间位置元素50，
由于50<70，所以这个时候我们需要向右继续查找，然后再取中间元素75，由于75>70所有向左查找，以此类推，63,69,72，71,70，所以，最终查找了7次，如果使用顺序查找的话，需要70次才能找到。所以
二分查找的时间复杂度从顺序查找的O(n)下降到了O(logn)，代码：

public class DemoMain {
    public static void main(String[] args) {
        int[] nums = new int[100];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = i * 2;
        }
        int i = find(nums, 70);
        System.out.println("下标：" + i);
    }
    public static int find(int[] nums,int x) {
        int start = 0;
        int end = nums.length;
        int count = 0;
        while (true) {
            int index = start + (end - start) / 2;
            count++;
            if(nums[index] == x){
                System.out.println("查找了：" + count + "次");
                return index;
            }
            if(nums[index] > x){
                end = index;
            }
            if(nums[index] < x){
                start = index;
            }
            if((end - start)==1){
                System.out.println("查找了：" + count + "次");
                System.out.println("没有找到");
                return 0;
            }
            System.out.println(nums[index]);
        }
    }
}

动态规划

字典树和并查集

高级搜索（剪枝，双向BFS）

红黑树和AVL树

如果一棵树的所有节点只有左子树或者只有右子树，那么就退化成了一个链表，链表的查询时间复杂度是线性的，也就是O(n)，在这种极端的情况下，二叉树的效率也会受到影响，所以才引申除了平衡二叉树。

  • AVL树：又称平衡二叉搜索树，它可以是一颗空树也可以是一颗左右子树的深度差绝对值小于等于1的二叉树，并且左右子树都是一颗平衡二叉树。
    1. 平衡因子：某节点的左右子树的深度差被称为平衡因子。平衡二叉搜索树的平衡因子只能是-1,0,1
    2. 在平衡二叉搜索树中添加节点有可能会导致其失去平衡，所以在每次插入的时候需要去调整，使之保持平衡二叉搜索树的特性。当一个节点的左右子树平衡因子绝对值大于1时，就需要进行调整。
      调整的方式有如下四种，分别对应几种场景：
      i. LL（右旋）：当某个节点的子树节点是左左型时，就需要向右旋转。
      i. RR（左旋）：当某个节点的子树节点是右右型时，就需要向左旋转。
      i. LR（左右旋）：当某个节点的子树节点是左右型时，就需要先向左旋转，再向右旋转。
      i. RL（右左旋）：当某个节点的子树节点是右左型时，就需要先向右旋转，再向左旋转。
    3. AVL树的缺点，强平衡导致每次插入节点时效率较低，因为每次都要去判断当前这棵树的平衡因子绝对值是否大于1，如果大于的话就需要进行平衡旋转。
  • 红黑树：又称RB树，为了避免每次插入都去调整整棵树的平衡，红黑树在AVL树的基础上做了优化，它是一颗近似平衡的二叉搜索树，旨在提交插入等操作的性能。它的节点性质如下：
    1. 节点只能是红色或黑色。
    2. 根节点必须是黑色。
    3. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
    4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
      也就是说，它可以容忍最高结点的高度不高于最低结点的高度的两倍，如果超越了该限制则触发平衡调整。

位运算

现代计算机的所有数据都是以二进制的形式存储在设备中的，也就是只有1,0两种状态。位运算符有六种：

  • &：按位与，如果两个位都为1，结果才为1
  • |：按位或，如果两个位都为0，结果才为0
  • ^：异或，两个位相同为0，相异为1
  • ~：取反，0变1,1变0
  • <<：左移，各二进位向左移动若干位（具体多少位由<<后面的数字指定），高位丢弃，低位补0
  • >>：右移，各二进位向右移动若干位（具体多少位由>>后面的数字指定），低位丢弃，高位用符号位补充
  • >>>：无符号右移，和右移的区别在于，不管当前是正号还是负号，高位都补0，低位丢弃

布隆过滤器和LRU缓存淘汰算法

排序算法

高级动态规划

字符串算法

上一篇： Nexus搭建Maven私服