Algorithm

算法概述

算法

• 在计算机领域里，算法是一系列程序指令，用于处理特定的运算和逻辑问题。衡量算法优劣的主要标准是时间复杂度和空间复杂度

数据结构

• 数据结构是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据
• 数据结构包含数组、链表这样的线性数据结构，也包含数、图这样的复杂数据结构

时间复杂度

• 时间复杂度是对一个算法运行时间长短的量度，用大 O 表示，记作 T(n) = O(f(n))
• 常见的时间复杂度按照从低到高的顺序，包括 O(1)、O(logn)、O(n)、O(logn)、O(n^2) 等

空间复杂度

• 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，用大 O 表示，记作 S(n) = O(f(n))
• 常见的空间复杂度按照从低到高的顺序，包括 O(1)、O(n)、O(n^2) 等。其中递归算法的空间复杂度和递归深度成正比

数据结构基础

数组

• 数组是由有限个相同类型的变量所组成的有序集合，它的物理存储方式是顺序存储，访问方式是随机访问。利用下标查找数组元素的时间复杂度是 O(1)，中间插入、删除数组元素的时间复杂度是 O(n)

链表

• 链表是一种链式数据结构，由若干节点组成，每个节点包含指向下一个节点的指针。链表的物理存储方式是随机存储，访问方式是顺序访问。查找链表节点的时间复杂度是 O(n)，中间插入、删除节点的时间复杂度是 O(1)

栈

• 栈是一种线性逻辑结构，可以用数组实现，也可以用链表实现。栈包含入栈和出栈操作，遵循先入后出的原则 (FILO)

队列

• 队列也是一种线性逻辑结构，可以用数组实现，也可以用链表实现。队列包含入队和出队操作，遵循先入先出的原则 (FIFO)

散列表

• 散列表也叫哈希表，是存储 Key-Value 映射的集合。对于某一个 Key，散列表可以在接近 O(1) 的时间内进行读写操作。散列表通过哈希函数实现 Key 和数组下标的转换，通过开放寻址法和链表法来解决哈希冲突

树

树

• 树是 n 个节点的有限集，有且仅有一个特定的称为根的节点。当 n > 1时，其余节点可分为 m 个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树

二叉树

• 二叉树是树的一种特殊形式，每一个节点最多有两个孩子节点。二叉树包含完全二叉树和满二叉树两种特殊形式

二叉树的遍历有几种

• 根据遍历节点之间的关系，可以分为前序遍历、中序遍历、后序遍历、层序遍历这四种方式；从更宏观的角度划分，可以划分为深度优先遍历和广度优先遍历两大类

二叉堆

• 二叉堆是一种特殊的完全二叉树，分为最大堆和最小堆
• 在最大堆中，任何一个父节点的值，都大于或等于它左、右孩子节点的值
• 在最小堆中，任何一个父节点的值，都小于或等于它左、右孩子节点的值

优先队列

• 优先队列分为最大优先队列和最小优先队列
• 在最大优先队列中，无论入队顺序如何，当前最大的元素都会优先出队，这是基于最大堆实现的
• 在最小优先队列中，无论入队顺序如何，当前最小的元素都会优先出队，这是基于最小堆实现的

排序算法

排序算法	平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定排序
冒泡排序	O(n^2)	O(n^2)	O(1)	稳定
鸡尾酒排序	O(n^2)	O(n^2)	O(1)	稳定
快速排序	O(nlogn)	O(n^2)	O(logn)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(1)	不稳定
计数排序	O(n+m)	O(n+m)	O(m)	稳定
桶排序	O(n)	O(nlogn)	O(n)	稳定