1 - 数据结构基本概念
了解数据结构的分类。
什么是数据结构
数据结构是数据对象的集合，以及数据对象之间的关系和在数据上的操作。
分类
- 线性结构：
- 数组：具有固定大小的数据元素的集合，这些元素在存储中是连续的，并可以通过索引访问。
- 链表：由节点组成，每个节点包含数据部分和指向下一个节点的指针。
- 栈：后进先出
(LIFO)的数据结构，只允许在顶部添加或删除元素。 - 队列：先进先出
(FIFO)的数据结构，允许在一端添加元素，并在另一端删除元素。
- 非线性结构
- 树：由节点组成的分层结构，其中有一个根节点，其他节点分为多个子树。
- 二叉树：每个节点最多有两个子节点。
- 平衡树、搜索树、红黑树
等是树的特殊类型。
- 图：由节点（或称为顶点）和边组成的结构。
- 树：由节点组成的分层结构，其中有一个根节点，其他节点分为多个子树。
- 散列结构：使用哈希函数将键转换为数组的索引，以便能够在常数时间内找到相关的值。
数据结构和算法
有效的算法通常依赖于选择合适的数据结构，而数据结构的实现和操作往往需要算法。
数据结构的选择直接影响到算法的性能。例如，数据的搜索在哈希表中可能是 O(1) 的复杂度，而在数组或链表中可能是 O(n) 的复杂度。
2 - 算法基本概念
需了解时间复杂度和空间复杂度的计算方法，是后续内容的基础。
什么是算法
算法 (Algorithm) 是一个明确规定了操作步骤的有限指令集，用于计算函数、处理数据、解决一个特定问题或执行某个任务。
算法的基本属性：
- 明确性：每一步骤必须有明确且不含糊的定义。
- 有输入和输出：算法应有0个或更多的输入和1个或更多的输出。输入是在算法开始之前提供的，而输出是在算法结束时产生的。
- 有限性：如果算法在执行完有限步骤后终止，那么它就是有限的。换句话说，一个算法必须总是在执行有限次操作后结束。
- 可行性：算法中的每一步都应该是简单且基本的，这样它们可以在有限的时间内完成并由计算机执行。
- 独立性：算法的指令应该有普适性，也就是说，它们不应依赖于任何特定的编程语言或模型。相反，算法应该足够通用，可以在任何编程环境中实现。
效率度量
时间复杂度
时间复杂度（Time Complexity）描述的是执行某个算法所需要的时间如何随着输入数据量的增长而变化。这是一个估计，通常只考虑最高阶的项，并忽略常数因子。常见的时间复杂度（按增长速度排序）有：
- $O(1)$：常数时间。无论输入数据有多大，算法都在恒定的时间内完成。
- $O(\log n)$：对数时间。例如：二分搜索。
- $O(n)$：线性时间。例如：简单的搜索算法。
- $O(n \log n)$：线性对数时间。例如：高效的排序算法，如归并排序。
- $O(n^2)$、$O(n^3)$ …：多项式时间。例如：冒泡排序、插入排序和选择排序是 (O(n^2)$。
- $O(2^n)$：指数时间。例如：计算斐波那契数列的递归实现。
- $O(n!)$：阶乘时间。例如：旅行商问题的暴力解决方法。
空间复杂度
空间复杂度（Space Complexity）描述的是执行某个算法所需要的存储空间如何随着输入数据量的增长而变化。与时间复杂度类似，我们只关心增长的速度，并通常只考虑最高阶的项。
例如：
- $O(1)$：算法使用恒定的额外空间。
- $O(n)$：算法的存储需求与输入数据的大小成线性关系。