算法入门基础知识

本文主要是介绍算法入门基础知识，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一般语言自带的常用数据结构：（不用语言的对应数据结构名称可能有所差异）

• 列表（list/array list/array等）。列表常见操作，以及相关的时间复杂度。
• append一个元素、pop末尾元素均为O（1）
• 查找某个元素的索引O（n）
• 哈希（hash table）。需要掌握以下基础知识：
• 什么是哈希，哈希函数是什么，最常见的哈希表数据结构是什么（集合与哈希表）
• 集合（set/ hashset等）。
• 集合一般用于干什么？
• 集合的常见操作有哪些？每个常见操作的时间复杂度是什么？
• 哈希表（Hashmap/ dict/ unordered_map等）。
• 哈希表一般用于干什么？
• 哈希表有哪些常见操作？对应的时间复杂度，空间复杂度分别是什么？
• 栈（stack）
• 什么是栈？什么是后进先出？
• 栈一般用于解决什么问题？
• 什么是程序栈？
• 你所熟悉的语言当中栈是用什么数据结构实现的？（Python当中用list就可以代表栈）
• 队列（queue）
• 什么是队列？什么是先进先出？
• 队列一般应用在哪些场景当中？
• 什么是消息队列？
• 你所熟悉的语言当中栈是用什么数据结构实现的？（Python当中可以用deque或者queue）
• 堆（heap）
• 什么是堆？什么是最大堆、最小堆？
• 堆一般用于解决什么问题？
• 你所熟悉的语言当中堆是用什么数据结构实现的？（Python当中堆用的是列表实现的，并且Python只有最小堆没有最大堆）

一般语言不自带的数据结构：（需要自己手工创建）

• 链表（linked list）
• 链表的节点（node）是如何实现的？
• 如何创建一个链表？
• 如何遍历一个链表？
• 如何在链表中查找一个元素是否存在？
• 如何在链表中添加/删除一个元素？
• 二叉树（binary tree）
• 二叉树的节点（node）是如何实现的？
• 如何创建一个二叉树？
• 如何遍历一个链表？何谓二叉树的层序、前序、中序、后序遍历？
• 二叉搜索树（二叉查找树、binary search tree、BST）
• 与普通的二叉树相比，二叉搜索树特点是什么？如何证明一棵二叉树是/不是一课二叉搜索树？
• 一个二叉树是二叉搜索树 <-> 该二叉树的中序遍历是单调递增的
• 简单图（graph）
• 什么是图？什么是有向图（directed graph）？什么是无向图（undirected graph）？
• 图与树的关系是？如何知道一个图是不是一课树？
• 如何实现一个简单图？

应该掌握的入门算法：

• 递归：
• 什么是递归？
• 递归的优势、劣势是什么？
• 递归三要素是什么？
• 排序算法：
• 快速排序如何实现？时间/空间复杂度是多少？
• 归并排序如何实现？时间/空间复杂度是多少？
• 二分法：
• 二分法的基本原理是什么？
• 二分法一般用于解决什么问题？
• 二分法的时间复杂度是什么？
• 宽度优先遍历（宽度优先搜索、Breadth first search、BFS）：
• 宽度优先遍历的模板是什么？
• 宽度优先遍历的时间/空间复杂度是什么？
• 宽度优先遍历一颗二叉树与一个图的区别在哪？
• 宽度优先遍历一般用于解决什么问题？
• 深度优先遍历（深度优先搜索、Depth first search、DFS）：
• 深度优先遍历的模板是什么？
• 深度优先遍历的时间/空间复杂度是什么？
• 深度优先遍历一颗二叉树与一个图的区别在哪？
• 深度优先遍历一般用于解决什么问题？

这篇关于算法入门基础知识的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！