小灰的漫画之旅学习笔记
- 衡量算法好坏的重要标准有两个：时间复杂度 和空间复杂度
- 数据结构（data structure）：是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据。
- 数据结构的组成方式
- 线性结构：数组、链表、栈、队列、哈希表
- 树：二叉树、二叉堆
- 图
- 其他：跳表、哈希链表、位图
- 若 存在 函数 f( n)， 使 得当 n 趋近 于 无穷大 时， T( n)/ f( n) 的 极 限值 为 不等于 零 的 常数， 则 称 f( n) 是 T( n) 的 同 数量级 函数。 记作 T( n)= O( f( n))， 称为 O( f( n))， O 为 算法 的 渐进 时间 复杂度， 简称 为 时间 复杂度。
魏梦舒. 漫画算法：小灰的算法之旅 (Kindle 位置 323-325). Kindle 版本.
-
推导出时间复杂度的几个原则：
- 如果 运行时 间 是 常数 量级， 则用 常数 1 表示
- 只 保留 时间 函数 中的 最 高阶 项
- 如果 最 高阶 项 存在， 则 省去 最 高阶 项 前面 的 系数
-
常见的空间复杂度：
- 常量空间
- 线性空间
- 二维空间
- 递归空间：纯粹的递归操作的空间复杂度也是线性的，如果递归深度是 n ，那么空间复杂度就是 O(n)
-
什么 是 算法
在 计算机 领域 里， 算法 是一 系列 程序 指令， 用于 处理 特定 的 运算 和 逻辑 问题。
衡量 算法 优劣 的 主要 标准 是 时间 复杂度 和 空间 复杂度。
-
什么 是 数据 结构
数据 结构 是 数据 的 组织、 管理 和 存储 格式， 其 使用 目的 是 为了 高效 地 访问 和 修改 数据。
数据 结构 包含 数组、 链 表 这样 的 线性 数据 结构， 也 包含 树、 图 这样 的 复杂 数据 结构。
-
什么 是 时间 复杂度
时间 复杂度 是对 一个 算法 运行 时间 长短 的 量度， 用 大 O 表示， 记作 T( n)= O( f( n))。
常见 的 时间 复杂度 按照 从低 到 高的 顺序， 包括 O( 1)、 O( logn)、 O( n)、 O( nlogn)、 O( n2) 等。
-
什么 是 空间 复杂度
空间 复杂度 是对 一个 算法 在 运行 过程中 临时 占用 存储 空间 大小 的 量度， 用 大 O 表示， 记作 S( n)= O( f( n))。
常见 的 空间 复杂度 按照 从低 到 高的 顺序， 包括 O( 1)、 O( n)、 O( n2) 等。 其中 递归 算法 的 空间 复杂度 和 递归 深度 成正比。
魏梦舒. 漫画算法：小灰的算法之旅 (Kindle 位置 453-454). Kindle 版本.
数组（array）是有限个相同类型的变量（针对强类型语言，如：Java）所组成的有序集合，适合：读操作多、写操作少的场景。
链表（linked list）是一种在物理上非连续、非顺序的数据结构，由若干节点（node）所组成，适合：频繁的插入、删除元素。
* 单向链表的每一个节点又包含两部分，一部分是存放数据的变量 data，另一部分是指向下一个节点的指针 next。
* 双向链表的每一个节点包含三部分，数据变量data、指向下一节点的next 指针以及指向前置节点的perv 指针。
物理结构：顺序存储结构（例如：数组）、链式存储结构（例如：链表）。
逻辑结构：线性结构（例如：顺序表、栈、队列）、非线性结构（例如：树、图）。
逻辑结构不影响使用的物理结构，例如栈和队列属于逻辑结构，它们的物理结构既可以利用数组，也可以使用链表来完成。
栈（ stack） 是一 种 线性 数据 结构，栈 中的 元素 只能 先入 后 出（ First In Last Out， 简称 FILO）。 最早 进入 的 元素 存放 的 位置 叫作 栈 底（ bottom）， 最后 进入 的 元素 存放 的 位置 叫作 栈 顶（ top）。
栈 这种 数据 结构 既可 以用 数组 来 实现， 也可以 用 链 表 来 实现。
队列（ queue） 是一 种 线性 数据 结构， 队列 中的 元素 只能 先入 先出（ First In First Out， 简称 FIFO）。 队列 的 出口 端 叫作 队 头（ front）， 队列 的 入口 端 叫作 队 尾（ rear）。
与 栈 类似， 队列 这种 数据 结构 既可 以用 数组 来 实现， 也可以 用 链 表 来 实现。
散 列表 也 叫作 哈 希 表（ hash table）， 这种 数据 结构 提供 了 键（ Key） 和 值（ Value） 的 映射 关系。 只要 给出 一个 Key， 就可以 高效 查 找到 它 所 匹配 的 Value， 时间 复杂度 接 近于 O( 1)。
对于 某一个 Key， 散 列表 可以 在 接近 O( 1) 的 时间 内 进行 读写 操作。 散 列表 通过 哈 希 函数 实现 Key 和数 组 下标 的 转换， 通过 开放 寻址 法 和 链 表 法 来 解决 哈 希 冲突。