数据结构与算法图解(最全知识点答案总结)

数据结构与算法图解(最全知识点答案总结)-mikechen
数据结构与算法是非常重要的内容,本文全面总结数据结构与算法相关的所有知识点,非常的全面@mikechen

数据结构

数据结构与算法图解(最全知识点答案总结)-mikechen

数组

数组是一种数据结构,用来存储同一类型的集合。

数据结构与算法图解(最全知识点答案总结)-mikechen

链表

链表是一种常见的数据结构,是一种线性表,是以节点的方式来存储, 是链式存储,是通过链表中的指针连接次序实现的。

数据结构与算法图解(最全知识点答案总结)-mikechen

栈:栈是一种计算机系统中的数据结构,它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶。

数据结构与算法图解(最全知识点答案总结)-mikechen

队列

队列是一种操作受限的线性表,只允许在表的前端(front)进行删除操作又称作出队,在表的后端进行插入操作,称为入队,符合先进先出(First in First out)的特性。在队尾插入元素叫做入队,对头删除元素叫做出队。

比如我们常用的 LinkedList 集合,它实现了Queue 接口,我们可以理解为 LinkedList 就是一个队列。

数据结构与算法图解(最全知识点答案总结)-mikechen

哈希表

哈希表,英文名为:Hash表,也称散列表,是根据键值而直接进行访问的数据结构。

哈希表它通过把键值(key-value)映射到表中一个位置来访问记录,以加快查找的速度,这个映射函数叫做散列函数,存放记录的数组叫做散列表。

数据结构与算法图解(最全知识点答案总结)-mikechen

 

二叉树

二叉树作为一种重要的树形结构类型,通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。

下图中这棵树,就是一颗典型的二叉查找树:

数据结构与算法图解(最全知识点答案总结)-mikechen

满足以下两个条件的树就是二叉树:

1)本身是有序树;

2)树中包含的各个节点的度不能超过 2,即只能是 0、1 或者 2。

二叉树还可以继续分类,衍生出满二叉树和完全二叉树,如下图所示:

1.满二叉树

棵树高度为h,高度为h,由2^h-1个节点构成的二叉树,就称为满二叉树,如下图所示:

数据结构与算法图解(最全知识点答案总结)-mikechen

2.完全二叉树

完全二叉树是由满二叉树而引出来的,如下图所示:

数据结构与算法图解(最全知识点答案总结)-mikechen

满二叉树最后一层都是满节点的,而完全二叉树不是。

 

算法分析

数据结构与算法图解(最全知识点答案总结)-mikechen

时间复杂度

时间复杂度是一个函数,它定性描述该算法的运行时间,时间复杂度常用大O符号表述。

大O时间复杂度并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势。

常见的时间复杂度,如下所示:

  1. 常数阶O(1);
  2. 线性阶O(n);
  3. 平方阶O(n²);
  4. 对数阶O(logn);
  5. 线性对数阶O(nlogn)

数据结构与算法图解(最全知识点答案总结)-mikechen

 

空间复杂度

空间复杂度,英文名为Space complexity,是指算法编写成程序后,在计算机中运行时所需存储空间大小的度量。

常见的空间复杂度,如下所示:

O(1) < O(log N) < O(N) < O(N^2) < O(2^N)

数据结构与算法图解(最全知识点答案总结)-mikechen

经典算法

数据结构与算法图解(最全知识点答案总结)-mikechen

递归算法

递归算法,就是自己调用自己,一个方法在执行过程中调用自身, 就称为 “递归”。

数据结构与算法图解(最全知识点答案总结)-mikechen

递归的常用算法伪代码如下:

func( mode){
    if(endCondition){      //递归出口
          end;
    }else{
         func(mode_small)  //调用本身,递归
    }
}

 

贪心算法

贪心算法,又名贪婪算法,是指在对问题求解时,总是做出在当前看来是最好的选择,从而希望能够导致结果是最好或者最优的算法。

 

分治算法

分治算法,字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题,直到最后子问题可以简单的直接求解。

数据结构与算法图解(最全知识点答案总结)-mikechen

 

动态规划算法

动态规划,英文名Dynamic Programming,是一种把原问题分解为相对简单的子问题以求解的方法。

动态规划算法:每次决策依赖于当前状态,个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。

 

贪婪算法

贪婪算法,英文名为Greedy Algorithm,又名贪心算法

贪婪算法,是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。

 

回溯算法

回溯算法,是一种选优搜索法,又称为试探法,按选优条件向前搜索以达到目标。

回溯算法简要说:但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法。

 

分支限界法算法

 

经典排序

数据结构与算法图解(最全知识点答案总结)-mikechen

插入排序

插入排序,英文名为InsertionSort,一般也被称为直接插入排序。

何谓插入排序:每次将一个待排序的记录,按其关键字大小插入到前面已经排序好的序列中,直到全部记录插入完成为止。

面我们看一个动图就会更加清楚。

下图所示:

数据结构与算法图解(最全知识点答案总结)-mikechen

冒泡排序

冒泡排序,英文名为Bubble Sort,是一种简单直观的排序算法。

冒泡排序,之所以叫做冒泡,因为每一个元素都可以像小气泡一样,根据自身大小一点一点向数组的一侧移动。

数据结构与算法图解(最全知识点答案总结)-mikechen

 

快速排序

快速排序,英文名为Quick Sort,是由C.A.R Hoarse 在1960年提出,是一种排序算法。

快速排序是从冒泡排序算法演变而来的,是对冒泡排序的一种改进,比选择排序快的多。

由于快速排序算法元素之间的比较次数较少,速度较快,因而得名快速排序。

如下动图所示:

数据结构与算法图解(最全知识点答案总结)-mikechen

 

选择排序

选择排序,英文名为Select Sort,选择排序是一种排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。

何谓选择排序:每次将一个待排序的记录,按其关键字大小插入到前面已经排序好的序列中,直到全部记录插入完成为止。

下图所示:

数据结构与算法图解(最全知识点答案总结)-mikechen

 

希尔排序

希尔排序,英文名为Shell’s Sort,是插入排序的一种,希尔排序,是希尔(Donald Shell)于1959年提出的一种排序算法。

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。

 

堆排序

堆排序,英文名为Heap Sort,是将数据看成近似完全二叉树结构,并根据完全二叉树的特性来进行排序的一种算法。

堆排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。

 

经典查找

经典查找:顺序查找、二分查找、二叉排序树查找

 

作者简介

陈睿|mikechen,10年+大厂架构经验,BAT资深面试官,就职于阿里巴巴、淘宝、百度等一线互联网大厂。

👇阅读更多mikechen架构文章👇

阿里架构 |双11秒杀 |分布式架构 |负载均衡 |单点登录 |微服务 |云原生 |高并发 |架构师

以上

关注作者「mikechen」公众号,获取更多技术干货!

后台回复架构,即可获取《阿里架构师进阶专题全部合集》,后台回复面试即可获取《史上最全阿里Java面试题总结

评论交流
    说说你的看法