01.数据结构与算法概述

在我们日常生活中我们已经在不知不觉中学会了许多算法，并习惯将它们应用到日常生活中了。

例一：查阅字典。在字典里，每个汉字都对应一个拼音，而字典是按照拼音字母顺序排列的。假设我们需要查找一个拼音首字母为 r 的字。

1. 翻开字典约一半的页数，查看该页的首字母是什么，假设首字母为 m。
2. 由于在拼音字母表中 r 位于 m 之后，所以排除字典前半部分，查找范围缩小到后半部分。
3. 不断重复步骤 1. 和 步骤 2. ，直至找到拼音首字母为 r 的页码为止。

1. 算法是什么

1.1 算法定义

「算法 algorithm」是在有限时间内解决特定问题的一组指令或操作步骤，它具有以下特性。

• 问题是明确的，包含清晰的输入和输出定义。
• 具有可行性，能够在有限步骤、时间和内存空间下完成。
• 各步骤都有确定的含义，相同的输入和运行条件下，输出始终相同。

1.2 数据结构定义

「数据结构 data structure」是计算机中组织和存储数据的方式，具有以下设计目标。

• 空间占用尽量减少，节省计算机内存。
• 数据操作尽可能快速，涵盖数据访问、添加、删除、更新等。
• 提供简洁的数据表示和逻辑信息，以便使得算法高效运行。

数据结构设计是一个充满权衡的过程。如果想要在某方面取得提升，往往需要在另一方面作出妥协。下面举两个例子：

• 链表相较于数组，在数据添加和删除操作上更加便捷，但牺牲了数据访问速度。
• 图相较于链表，提供了更丰富的逻辑信息，但需要占用更大的内存空间。

1.3 数据结构和算法的关系

如图所示，数据结构与算法高度相关、紧密结合，具体表现以下三个方面：

• 数据结构是算法的基石。数据结构为算法提供了结构化存储的数据，以及用于操作数据的方法。
• 算法是数据结构发挥作用的舞台。数据结构本身仅存储数据信息，结合算法才能解决特定问题。
• 算法通常可以基于不同的数据结构进行实现，并往往有对应最优的数据结构，但最终执行效率可能相差很大。

算法复杂度：时间和空间复杂度，衡量算法效率，算法在执行过程中，随着数据规模n的增长，算法执行所花费的时间和空间的增长速度。

常见的时间复杂度：

大 O 计法	应用实例
O(1)	数组随机访问、哈希表
O($log_n$)	二分搜索、二叉树调整、AVL、红黑树查找
O(n)	线性搜索
O($nlog_n$)	堆排序、快速排序、归并排序
O($n^2$)	冒泡排序、选择排序、插入排序
O($2^n$)	子树集
O(n!)	排列树
常见算法的时间复杂度关系：O(1) < O($log_n$) < O(n) < O($nlog_n$) < O($n^2$) < O($2^n$) < O(n!) < O($n^n$)